Union-Find算法

发表于 | 分类于 | 阅读次数

1.简介

Union-Find算法又称并查集算法，是一种作用于并查集数据结构的算法。包含两个主要的操作：

  • Find 用于查找某个元素属于哪个集合，可以用来确定两个元素是否在同一个集合中；
  • Union 用于合并两个不同的集合；

2.原理

并查集数据结构是一种树形结构，树形结构对于有规律的数据组织方式，进行修改和查找十分高效。
具体结构如下图一所示：



图一





图二


图一展示了并查集的树形结构，每一棵独立的树都代表一个独立的集合，在同一棵树下的所有节点自然就是属于同一个集合。
图二表示了并查集的存储结构，并查集数据结构采用数据对树进行存储，元素i的值id[i]存储的是其在树形结构上对应的父节点的标号，而根节点元素root的值id[root]是本身的标号，即root = id[root];

有了上述的树形结构和数据的组织形式后，一些基本的操作就变得简单了。

  • root(x) 返回元素x所在树的根节点，从当前元素x的父节点id[i]不断的向上递推求父节点，直到id[i] == i成立。
  • connected(x, y)判断x和y元素是否是连通的（直接或间接）,只需要判断两个节点是否有相同的根节点（即是否在同一棵树中）；
  • count(x) 获取元素x所在集合（树）的元素（节点）的个数,以根节点来分别统计每棵树的节点的数目；
  • find(x) 返回元素x的根节点
  • union(x,y) 将元素x和y连通，将x所在的树的拼接到y所在树种，（反之亦可）即将x的根节点父节点设置为y的根节点。

上述的操作基本上覆盖了并查集数据结构以及算法中的大部分操作，由此可以写出一个基本的并查集算法雏形：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class UnionFind {
	
	private int[] id;
	
	public UnionFind(int size) {
		id = new int[size];
		for (int i = 0; i < size; i++) {
			id[i] = i;
		}
	}
	
	public boolean connected(int i, int j) {
		return root(i) == root(j);
	}
	
	private int root(int i) {
		int root;
		while ((root = id[i]) != i)
			i = id[i];	
		return root;
	}
	
	public int find(int i) {
		return root(i);
	}
	
	public void union(int i, int j) {
		int rootI, rootJ;
		if ((rootI = root(i)) == (rootJ = root(j)))
			return;
     id[rootI] = rootJ;//将i节点所在树移接到j节点所在树
	}
	
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		Map<Integer, List<Integer>> group = new HashMap<>();
		for (int i = 0 ; i < this.id.length; i++) {
			int root = root(i);
			if (group.get(root) == null) {
				List<Integer> tmp = new ArrayList<>();
				tmp.add(i);
				group.put(root, tmp);
			} else 
				group.get(root).add(i);
		}
		return group.toString();
	}
}

3.改进

对上述Union-Find的两个主要操作find和union的时间复杂度进行分析易得出

  • union(i,j) — O(1)
  • find(i) — O(h) 其中h是节点i所在树的高度

由于在进行对两个节点进行union操作的时候，我们总是不加选择的将节点i所在的树拼接到节点j所在的树下，这样可能会导致某一棵树特别的瘦高，即其h很大，几乎可以接近于n，从而可能导致find操作可能需要遍历整个集合。



图三


由于这个原因，我们需要不断的调整树，使其变得稍微矮胖一些，如图四。



图四


为了将树摊平，存在两个改进的地方：

  • 带权的union操作 即在进行union操作的时候，可以先判断节点所在树的大小，将size小的树接到size大的树；

  • 路径压缩 即在进行find操作的时候，在找到根节点后，循环将该路径下的所有节点都拼接到根节点下，如图五所示；

    ​



    图五




图六


改进后union-find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

class UnionFind {
	
	private Map<Integer, Integer> memSize;
	private int[] id;
	
	public UnionFind(int size) {
		memSize = new HashMap<>();
		id = new int[size];
		for (int i = 0; i < size; i++) {
			id[i] = i;
			memSize.put(i, 1);
		}
	}
	
	public boolean connected(int i, int j) {
		return root(i) == root(j);
	}
	
	private int root(int i) {
		int root;
		while ((root = id[i]) != i) {
			//优化二：路径压缩，将当前非root节点i 拼接到爷节点下面，将爷节点作为自己的父节点
			//这样为后续查找节点i的root节点压缩路径深度，节约了时间。
			id[i] = id[id[i]];
			i = id[i];	
		}
    
    //或者另一种路径压缩方式
    /* while (id[i] != i) {
      id[i] = root;
      i = id[i];
    } */
    
		return root;
	}
	
	public int find(int i) {
		return root(i);
	}
	
	public void union(int i, int j) {
		int rootI, rootJ;
		if ((rootI = root(i)) == ( rootJ = root(j)))
			return;
		int iSize, jSize;
		//优化一：带权union, 小树接大树，避免新树过高；
		if ((iSize = memSize.get(rootI)) > (jSize = memSize.get(rootJ))) {
			id[rootJ] = rootI;
			memSize.put(rootI, iSize + jSize);
		} else {
			id[rootI] = rootJ;
			memSize.put(rootJ, iSize + jSize);
		}
	}
	
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		Map<Integer, List<Integer>> group = new HashMap<>();
		for (int i = 0 ; i < this.id.length; i++) {
			int root = root(i);
			if (group.get(root) == null) {
				List<Integer> tmp = new ArrayList<>();
				tmp.add(i);
				group.put(root, tmp);
			} else 
				group.get(root).add(i);
		}
		return group.toString();
	}
}

4.应用

  • Percolation.
  • Games (Go, Hex).
  • Dynamic connectivity.
  • Least common ancestor.
  • Equivalence of finite state automata.
  • Hoshen-Kopelman algorithm in physics.
  • Hinley-Milner polymorphic type inference.
  • Kruskal’s minimum spanning tree algorithm.
  • Compiling equivalence statements in Fortran.
  • Morphological attribute openings and closings.
  • Matlab’s bwlabel() function in image processing.

    5.References

    [1] Algorithms - Robert Sedgewick, Kevin Wayne