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