高级数据结构（Ⅰ）并查集（Union-Find）

╰半橙微兮° 2022-11-19 11:29 7阅读 0赞

## 高级数据结构（Ⅰ）并查集（union-find） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

### 动态连通性 ###

问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，一对整数p和q可以被理解为“p和q是相连的”。我们假设“相连”是一种等价关系，这意味着它具有：

*  自反性：p和p是相连的
 *  对称性：如果p和q是相连的，那么q和p也是相连的
 *  传递性：如果p和q是相连的且q和r是相连的，那么p和r也是相连的

等价关系能够将对象分为多个等价类。在这里，当且仅当两个对象相连时它们才属于同一个等价类。我们的目标是编写一个程序来过滤掉序列中所有无意义的整数对（两个整数均来自与同一个等价类中）。为了达到所期望的效果，我们需要设计一个数据结构来保存程序已知的所有整数对的足够多的信息，并用它们来判断一对象是否是相连的。我们将这个问题通俗地叫做**动态连通性**问题。

本文中以下内容中使用网络方面的术语，将对象称为**触点**，将整数对称为**连接**，将等价类称为**连通分量**或是简称**分量**。简单起见，假设我们有用`0`到`N - 1` 整数所表示的N个触点。这样做并不会降低算法的通用性。

### union-find算法API ###

为了说明问题，我们设计了一份API来封装所需的基本操作：初始化、连接两个触点、判断包含某个触点的分量、判断两个触点是否存在于同一个分量之中以及返回所有分量的数量。详细的API如下表所示

<table> 
 <thead> 
  <tr> 
   <th align="left">public class UF</th> 
   <th align="left">解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><code>UF(int N)</code></td> 
   <td align="left">以整数标识（0到N- 1）初始化N个触点</td> 
  </tr> 
  <tr> 
   <td align="left"><code>void union(int p, int q)</code></td> 
   <td align="left">在p和q之间添加一条连接</td> 
  </tr> 
  <tr> 
   <td align="left"><code>int find(int p)</code></td> 
   <td align="left">p（0到N-1）所在的分量标识符</td> 
  </tr> 
  <tr> 
   <td align="left"><code>boolean connected(int p, int q)</code></td> 
   <td align="left">如果p和q处于同一个连通分量中则返回true</td> 
  </tr> 
  <tr> 
   <td align="left"><code>int count()</code></td> 
   <td align="left">连通分量的数量</td> 
  </tr> 
 </tbody> 
</table>

为解决动态连通性问题设计算法的任务变成了实现这份API，所有的实现都应该：

*  定义一种数据结构表示已知的连接
 *  基于此数据结构实现高效的`union()`、`find()`、`connected()` 和 `count()` 方法

数据结构的性质将直接影响到算法的效率，因此数据结构和算法的设计时紧密相关的。API已经说明触点和分量都会用int值表示，所以我们可以用一个`以触点为索引`的`数组id[]`作为基本数据结构来表示所有分量。我们将使用分量中的某个触点的名称作为分量的标识符，因此你可以认为每个分量都是由它的触点之一所表示的。一开始，我们有N个分量，每个触点都构成了一个只含有它自己的分量，因此我们将`id[i]`的值初始化为`i`，其中`i`在0到N-1之间。对于每个触点`i`，我们将find()方法用来判定它所在的分量所需的信息保存在`id[i]`之中。connected()方法的实现只用一条语句`find(p) == find(q)`，它返回一个布尔值，我们在所有方法的实现中都会用到connected()方法。find()方法和union()方法的实现是以下内容要讨论的重点。

#### `union-find`的实现 ####

public class UF {
        
    	private int[] id;    //分量id(以触点作为索引)
    	private int count;   //分量数量
    	
    	public UF(int N) {
        
    		//初始化分量id数组
    		count = N;
    		id = new int[N];
    		for(int i = 0; i < N; i++) {
        
    			id[i] = i;
    		}
    	}
    	
    	public int count() {
        
    		return count;
    	}
    	
    	public boolean connected(int p, int q) {
        
    		return find(p) == find(q);
    	}
    	
    	public int find(int p) {
        
    		//见 quick-find、qucik-union、加权uick-union
    		return -1;    //省略此条代码
    	}
    	
    	public void union(int p, int q) {
        
    		//见 quick-find、qucik-union、加权uick-union
    	}
    	
    	public static void main(String[] args) {
        
    		//解决输入的连通性问题
    		Scanner sc = new Scanner(System.in);
    		int N = sc.nextInt();    //读取触点数量
    		UF uf = new UF(N);
    		while(sc.hasNext()) {
        
    			int p = sc.nextInt();
    			int q = sc.nextInt();   //读取整数对
    			if(uf.connected(p, q)) continue;   //如果已连通则忽略
    			System.out.println("(" + p + ", " + q + ")");  //打印连接
    		}
    		System.out.println(uf.count() + "components");
    	}
    }

**union-find的成本模型**：在研究实现union-find的API的各种算法时，我们统计的是`数组的访问次数`（访问任意数组元素的次数，无论读写）

### quick-find算法 ###

此方法保证当且仅当`id[p]` 等于 `id[q`\]时p和q是连通的。换句话说，在同一个连通分量中的所有触点在`id[]`中的值必须全部相同。这意味着`connected(p, q)`只需要判断i`d[p] == id[q]`，当且仅当p和q在同一连通分量之中该语句才会返回true。为了调用union(p, q)确保这一点，我们首先要检查它们是否已经存于同一个连通分量之中。如果存在于同一分量中我们不需要采取任何行动，否则我们面对的情况就是p所在的连通分量中的所有触点的`id[]`值均为同一个值，而q所在的连通分量中的所有触点的id\[\]均为另一个值。要将两个分量合二为一，我们必须将两个集合中所有触点对应的`id[]`元素变为同一个值。为此，我们需要遍历整个数组，将所有和`id[p]`相等的元素的值变为`id[q]`的值。我们也可以将所有和`id[q]`相等的元素的值变为i`d[p]`的值，两者均可。详细代码如下所示

public class QuickFindUF {
        
    	private int[] id;    //分量id(以触点作为索引)
    	private int count;   //分量数量
    	
    	public QuickFindUF(int N) {
        
    		//初始化分量id数组
    		count = N;
    		id = new int[N];
    		for(int i = 0; i < N; i++) {
        
    			id[i] = i;
    		}
    	}
    	
    	public int count() {
        
    		return count;
    	}
    	
    	public boolean connected(int p, int q) {
        
    		return find(p) == find(q);
    	}
    	
    	public int find(int p) {
        
    		return id[p];
    	}
    	
    	public void union(int p, int q) {
        
    		//将p和q归并到相同的分量中
    		int pID = find(p);
    		int qID = find(q);
    		
    		//如果p和q已经在相同的分量之中则不需要采取任何行动
    		if(pID == qID) return;
    		
    		//将p的分量重命名为q的名称
    		for(int i = 0; i < id.length; i++) {
        
    			if(id[i] == pID) id[i] = qID;
    		} 
    		count--;
    	} 
    }

测试数据及`id[]`值代码轨迹如下所示

边(p,q)            id[]
    p  q -|- 0  1  2  3  4  5  6  7  8  9
    -------------------------------------
    4  3 -|- 0  1  2  3  3  5  6  7  8  9
    3  8 -|- 0  1  2  8  8  5  6  7  8  9
    6  5 -|- 0  1  2  8  8  5  5  7  8  9
    9  4 -|- 0  1  2  8  8  5  5  7  8  8
    2  1 -|- 0  1  1  8  8  5  5  7  8  8
    8  9 -|- 0  1  1  8  8  5  5  7  8  8   此时不用做任何改变，8与9已结处于同一个连通分量中
    5  0 -|- 0  1  1  8  8  0  0  7  8  8 
    7  2 -|- 0  1  1  8  8  0  0  1  8  8 
    6  1 -|- 1  1  1  8  8  1  1  1  8  8
    1  0 -|- 1  1  1  8  8  1  1  1  8  8   此时不用做任何改变，1与0已结处于同一个连通分量中
    6  7 -|- 1  1  1  8  8  1  1  1  8  8   此时不用做任何改变，6与7已结处于同一个连通分量中

### quick-union算法 ###

此算法重点提高`union()`方法的速度，它和`quick-find`算法是互补的。它也基于相同的数据结构----**以触点作为索引的id\[\]数组**，但我们赋予这些值的意义不同，我们也需要用它们来定义更加复杂的结构。确切地说，每个触点对应的`id[]`元素都是同一个分量中另一个触点的名称（也可能是它自己）----我们将这种联系称为**链接**。在实现`find()`方法时，我们从给定的触点开始，由它的链接得到另一个触点，再由这个触点到达第三个触点，如此继续跟随着链接直到到达一个**根触点**，即链接指向自己的触点（这样的触点必然存在）。当且仅当分别由两个触点开始的这个过程到达了同一个根触点时它们存在于同一个连通分量中。为了保证这个过程的有效性，我们需要`union(p, q)`来保证这一点。它的实现很简单：我们由p和q的链接分别找到它们的根触点，然后只需将一个根触点连接到另一个根触点即可将一个分量重命名为另一个分量，因此这个算法叫做**quick-union**。和刚才一样，无论是重命名含有p的分量还是重命名含有q的分量都可以。

详细代码实现如下

public class QuickUnionUF {
        
    	private int[] id;    //分量id(以触点作为索引)
    	private int count;   //分量数量
    	
    	public QuickUnionUF(int N) {
        
    		//初始化分量id数组
    		count = N;
    		id = new int[N];
    		for(int i = 0; i < N; i++) {
        
    			id[i] = i;
    		}
    	}
    	
    	public int count() {
        
    		return count;
    	}
    	
    	public boolean connected(int p, int q) {
        
    		return find(p) == find(q);
    	}
    	
    	public int find(int p) {
        
    		//找出分量的名称
    		while(p != id[p]) p = id[p];
    		return p;
    	}
    	
    	public void union(int p, int q) {
        
    		//将p和q的根节点统一
    		int pRoot = find(p);
    		int qRoot = find(q);
    		if(pRoot == qRoot) return;
    		
    		id[pRoot] = qRoot;
    		
    		count--;
    	} 
    }

测试数据及`id[]`值代码轨迹如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]

### 加权quick-union算法 ###

与其在union()中随意将一棵树连接到另一棵树，我们现在会记录每一棵树的大小并总是将`较小的树连接到较大的树上`。这项改动需要添加一个数组和一些代码来记录树中的结点数，它能够大大改进算法的效率，提高了查询根触点的速度。该算法构造的树的高度远远小于未加权的版本所构造的树的高度。

详细代码实现如下

public class WeightedQuickUnionUF {
        
    	private int[] id;    //父链接数组(由触点索引)
    	private int[] sz;    //(由触点索引的)各个根节点所对应的分量的大小
    	private int count;   //连通分量的数量
    	
    	public WeightedQuickUnionUF(int N) {
        
    		count = N;
    		id = new int[N];
    		for(int i = 0; i < N; i++) id[i] = i;
    		sz = new int[N];
    		for(int i = 0; i < N; i++) sz[i] = 1;
    	}
    	
    	public int count() {
        
    		return count;
    	}
    	
    	public boolean connected(int p, int q) {
        
    		return find(p) == find(q);
    	}
    	
    	public int find(int p) {
        
    		//跟随连接找到根节点
    		while(p != id[p]) p = id[p];
    		return p;
    	}
    	
    	public void union(int p, int q) {
        
    		int pRoot = find(p);
    		int qRoot = find(q);
    		if(pRoot == qRoot) return;
    		
    		//将小树的根节点连接到大树的根节点
    		if(sz[pRoot] < sz[qRoot]) {
        
    			id[pRoot] = qRoot;
    			sz[qRoot] += sz[pRoot]; 
    		}else {
        
    			id[qRoot] = id[pRoot];
    			sz[pRoot] += sz[qRoot];
    		}
    		count--;
    	}
    }

测试数据及`id[]`值代码轨迹如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]

### 使用路径压缩的加权quick-union算法 ###

理想情况下，我们都希望每个节点都直接链接到它的根节点上，但我们又不想像quick-union算法那样通过修改大量链接来做到这一点。我们接近这种理想状态的方式很简单，就是在检查节点的同时将他们直接链接到根节点。这种方法的实现很容易，而且这些树并没有阻止我们进行这种修改的特殊结构：如果这么做能够改进算法的效率，我们就应该实现它。要实现路径压缩，只需要为find()添加一个循环，`将在路径上遇到的所有结点都直接链接到根节点`。我们所得到的结果是几乎完全扁平化的树，它和quick-find算法理想情况下所得到的树非常接近。这种方法既简单又高效，但在实际情况下已经不太可能对加权quick-union算法继续进行任何改进了。

`路径压缩的加权quick-union算法是最优的算法`

详细代码实现如下

public class PathCondenseWeightedQuickUnionUF {
        
    	private int[] id;    //父链接数组(由触点索引)
    	private int[] sz;    //(由触点索引的)各个根节点所对应的分量的大小
    	private int count;   //连通分量的数量
    	
    	public PathCondenseWeightedQuickUnionUF(int N) {
        
    		count = N;
    		id = new int[N];
    		for(int i = 0; i < N; i++) id[i] = i;
    		sz = new int[N];
    		for(int i = 0; i < N; i++) sz[i] = 1;
    	}
    	
    	public int count() {
        
    		return count;
    	}
    	
    	public boolean connected(int p, int q) {
        
    		return find(p) == find(q);
    	}
    	
        /*递归版本
    	public int find(int p) {
    		if(id[p] == p) return p;
    		id[p] = find(id[p]);
    		return id[p];
    	}
    	*/
    	
    	public int find(int p) {
        
    		int root = p;
    		while (root != id[root]) {
        
    			root = id[root];
    		}
    		while (id[p] != root) {
        
    			int temp = p;
    			p = id[p];
    			id[temp] = root;
    		}
    		return root;
    	}
    	
    	public void union(int p, int q) {
        
    		int pRoot = find(p);
    		int qRoot = find(q);
    		if(pRoot == qRoot) return;
    		
    		//将小树的根节点连接到大树的根节点
    		if(sz[pRoot] < sz[qRoot]) {
        
    			id[pRoot] = qRoot;
    			sz[qRoot] += sz[pRoot]; 
    		}else {
        
    			id[qRoot] = id[pRoot];
    			sz[pRoot] += sz[qRoot];
    		}
    		count--;
    	}
    }

测试数据及`id[]`值代码轨迹如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 3]

### 算法比较 ###

各种union-find算法的性能特点（存在N个触点时成本的增长数量级（最坏情况下））

<table> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>构造函数</th> 
   <th>union( )</th> 
   <th>find( )</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>quick-find算法</td> 
   <td>N</td> 
   <td>N</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>quick-union算法</td> 
   <td>N</td> 
   <td>树的高度</td> 
   <td>树的高度</td> 
  </tr> 
  <tr> 
   <td>加权quick-union算法</td> 
   <td>N</td> 
   <td>lgN</td> 
   <td>lgN</td> 
  </tr> 
  <tr> 
   <td>使用路径压缩的加权quick-union算法</td> 
   <td>N</td> 
   <td>非常接近但仍没有达到1（均摊成本）</td> 
   <td>接近1</td> 
  </tr> 
  <tr> 
   <td>理想情况</td> 
   <td>N</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
 </tbody> 
</table>

--------------------

参考资料：《算法》第四版

--------------------

### 并查集 > 左神版 ###

下面附左神《程序员代码面试指南》中并查集的实现代码

class Element<V> {
        
    	public V value;
    	public Element(V value) {
        
    		this.value = value;
    	}
    }
    
    public class UnionFindSet<V> {
        
    	public HashMap<V, Element<V>> elementMap;
    	public HashMap<Element<V>, Element<V>> fatherMap;
    	public HashMap<Element<V>, Integer> rankMap;
    	
    	public UnionFindSet(ArrayList<V> list) {
        
    		elementMap = new HashMap<>();
    		fatherMap = new HashMap<>();
    		rankMap = new HashMap<>();
    		for(V value : list) {
        
    			Element<V> element = new Element<V>(value);
    			elementMap.put(value, element);
    			fatherMap.put(element, element);
    			rankMap.put(element, 1);
    		}
    	}
    	
    	private Element<V> findHead(Element<V> element) {
        
    		Stack<Element<V>> path = new Stack<>();
    		while(element != fatherMap.get(element)) {
        
    			path.push(element);
    			element = fatherMap.get(element);
    		}
    		while(!path.isEmpty()) {
        
    			fatherMap.put(path.pop(), element);
    		}
    		return element;
    	}
    	
    	public boolean isSameSet(V a, V b) {
        
    		if(elementMap.containsKey(a) && elementMap.containsKey(b)) {
        
    			return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
    		}
    		return false;
    	}
    	
    	public void union(V a, V b) {
        
    		if(elementMap.containsKey(a) && elementMap.containsKey(b)) {
        
    			Element<V> aF = findHead(elementMap.get(a));
    			Element<V> bF = findHead(elementMap.get(b));
    			if(aF != bF) {
        
    				Element<V> big = rankMap.get(aF) >= rankMap.get(bF) ? aF : bF;
    				Element<V> small = big == aF ? bF : aF;
    				fatherMap.put(small, big);
    				rankMap.put(big, rankMap.get(aF) + rankMap.get(bF));
    				rankMap.remove(small);
    			}
    		}
    	}
    	
    }

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/795b287a02624814adfff1828b7895fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/0b8fdd9823f649c1972c490a085fba0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221119/dd94e8e6a5274868b7490641bb671d2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221119/a2aa41b794bd459aa4bab6b73d4a750d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221119/1522785e38954d3183e40a5e91baf4e6.png