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
50
| 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;
}
@Override
public String toString() {
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-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
73
74
|
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) {
id[i] = id[id[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;
int iSize, jSize;
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() {
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