算法原理系列：并查集

算法原理系列：并查集

《算法》当中第一章节就介绍了该数据结构，但并不知道它到底有何用，也就一直没有研究它。当做过一系列数组+链表+树的题目之后，再看看这并查集似乎又有点意思了，今天就探寻下。

　介绍

我对并查集的具体应用还不了解，所以就从一些基本的题目引出并查集。

并查含义：合并集合，查找集合。

可以有的操作如下：

• 给定两个“结点”，检查它们是否同属一个集合。（在同一集合中，所有元素均同质，因此判断两个元素是否属同集合是分类分组的前提。）
• 给定两个“结点”，把它们归并到同一集合中。（所以说，这些集合都有些共同特性，才能归在一起吧）
• 给定某个“结点”，判断它属哪个集合。（如果集合有唯一标识的话，我们可以实现该操作）

所以基本的并查集API如下：

public class UF {int[] union;public UF(int N) {union = new int[N];for (int i = 0; i < N; i++){union[i] = i;}}public void union(int p, int q){}public int find(int p){return 0;}public boolean connected(int p, int q){return false;}public int count(){return 0;}public static void main(String[] args) {In in = new In("./data/tinyUF.txt");int N = in.readInt();UF uf = new UF(N);for (int i = 0; i < N; i++){int p = in.readInt();int q = in.readInt();if (uf.connected(p, q)) continue;uf.union(p,q);System.out.println(p + " " + q);}System.out.println(uf.count() + " components");}}

union的数据结构采用数组形式，数组有两个天然的标识：index和value，所以在并查集应用中，由于index均唯一，所以它们可以代表每一个元素，而value则可以表示集合。

实现一（quick-find）

既然，我们能够对数组中的每个value进行操作，且初始化时，所有元素都有一个唯一的集合。union[i] = i，那么我们就用这唯一的i作为集合标识。比如：当需要连接p和q时，我们进行如下操作：

union[q] = q -> union[q] = p;此时集合p中的元素有所以，后续一旦有新的元素要加入到集合p中，如union(x,y)
int id = find(x);
union[y] = id;

代码如下：

public class UF {int[] union;int SIZE;public UF(int N) {union = new int[N];for (int i = 0; i < N; i++){union[i] = i;}SIZE = N;}public void union(int p, int q){int x = find(p);int y = find(q);if (x == y) return;for (int i = 0; i < union.length; i++){if (union[i] == y) union[i] = x;}SIZE --;}public int find(int p){return union[p];}public boolean connected(int p, int q){return find(p) == find(q);}public int count(){return SIZE;}public static void main(String[] args) {In in = new In("./data/tinyUF.txt");int N = in.readInt();UF uf = new UF(N);for (int i = 0; i < N; i++){int p = in.readInt();int q = in.readInt();if (uf.connected(p, q)) continue;uf.union(p,q);System.out.println(p + " " + q);}System.out.println(uf.count() + " components");}
}

关键在于union中的代码，为了维护元素所属的集合，在合并集合时：

p集合 
q集合 union(p2,q1)操作
需要更新q集合中的每个元素，把它们对应的值改为p。在代码实现中更加糟糕，需要遍历整个数组一次，所以：union操作复杂度：O(n)
find操作复杂度： O(1)

一种基于数组的扁平结构，虽然find非常快，但对于合并操作真的是太糟糕了，可不可以加快合并？

实现二（quick-union）

在union操作中，为了维护这种扁平结构，需要循环遍历一次数组，这种操作相当费时。熟悉树的话，我们知道，对两棵树的合并相当简单，只要把一棵树依附到某个结点上，就能合并成一棵更大的树。

而对于任何子结点而言，如果我们能追根溯源到根结点，那么就认为这些结点都属于同一棵树，这意义巨大，同一棵树我们即可表示为同一集合，因为任何结点在这棵树中的归属一致。（通过find手段找到同根）

所以quick-union的合并思路和树的合并一个道理，union(p,q)，p和q可以分别表示在存在于某棵树的两个中间结点，找到它们的根结点后，把一棵根结点树并到另一个根结点的孩子上。

嗯，数组可以用来表示森林，在堆中我们还知道数组可以表示成严格的完全二叉树。可见数组不仅仅是数组啊！

代码如下：

public void union(int p, int q){int pid = find(p);int qid = find(q);if (pid == qid) return;union[qid] = pid;SIZE--;}public int find(int p){while (p != union[p]){p = union[p];}return p;}

在平均情况下，union操作和find操作已经相当不错了，起码它们的时间复杂度为树的高度。可以参看《算法》P147页的时间复杂度分析。

但森林的构建非常依赖于输入union操作的顺序，在最坏情况下，可能会出现深度为N的一棵树，此时它的find操作就退化成了$O(n)$，而union依赖find，也成了$O(n)$，与其这样还不如再做点优化，稳定树的生长深度。

实现三（加权quick-union）

在最坏情况下，quick-union的深度即为结点数。这是因为在合并操作时，总是把大树依附在小树的结点上。所以为了规避上述这种情况，一种可行的方案就是把当遇到大树依附小树的情况，进行反向操作，让小树依附在大树上。

代码如下：

public class WeightedQuickUnionUF {int[] id;int[] sz;int count;public WeightedQuickUnionUF(int N){count = N;id = new int[N];sz = new int[N];for (int i = 0; i < N; i++) id[i] = i;for (int i = 0; i < N; i++) sz[i] = 1;}public void union(int p, int q){int pid = find(p);int qid = find(q);if (pid == qid) return;if (sz[pid] < sz[qid]){id[pid] = qid;sz[qid] += sz[pid];}else{id[qid] = pid;sz[pid] += sz[qid];}count --;}public boolean connect(int p, int q){return find(p) == find(q);}public int find(int p){while (p != id[p]){p = id[p];}return p;}public int count(){return count;}public static void main(String[] args) {In in = new In("./data/largeUF.txt");int N = in.readInt();UF uf = new UF(N);for (int i = 0; i < N; i++){int p = in.readInt();int q = in.readInt();if (uf.connected(p, q)) continue;uf.union(p,q);//System.out.println(p + " " + q);}System.out.println(uf.count() + " components");}}

一开始我以为sz是用来记录当前集合的高度，但不然，它记录的是当前集合的个数。这点很神奇，当把集合个数小的（小树）合并到集合个数大的大树上时，它就能规避最坏的情况。

对我来说有两点疑问：

• 集合个数和树的高度是否等价？
• 为什么把小树合并到大树上就能保证最坏情况不会出现，如何证明？

要回答第一个问题，先得解决第二个问题，第二个问题比较简单。出现最坏情况的原因在于每当进行union操作时，树的深度就+1，树深度+1何时会出现？当且仅当大树依附在小树上，此时树的深度一定更新为1+大树深度，因为小树深度<大树深度，所以合并操作导致树的高度变大。

我们的目标是尽量维持树的深度，如小树树高为3，大树树该为5，那么我们可以让小树依附在大树上，此时整棵树的高度没有增加依旧为5。

那为什么用元素个数来衡量树高同样可以保证算法正确呢？
归纳假设，在初始时，所有结点自成一派，元素个数为1，高度也为1，保证了find的高效性。

假设size小的集合，树的高度也较小，那么进行一轮合并得到新的集合时，高度不会增加。所以只要按照这种顺序更新，即能规避最坏情况。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！