概念

其实并查集顾名思义就是有“合并集合”和“查找集合中的元素”两种操作的关于数据结构的一种算法。

用途

1. 维护无向图的连通性。支持判断两个点是否在同一连通块内。
2. 判断增加一条边是否会产生环：用在求解最小生成树的Kruskal算法里。

操作

并查集主要就三个操作：初始化、合并、查找

初始化

一般来说，并查集的初始化用数组即可，例如数组Tree[i]，i表示某节点，tree[i]表示当前节点的根节点

查找函数

这里的查找和java集合类List中的查找函数get()并不一样，他的作用是查找该节点的根节点，如果集合的parent等于集合的编号（即还没有被合并或者没有同类），那么自然返回自身编号。如果不同那么就可以调用递归函数。

代码如下

 // 并查集查找根节点
 static int findRoot(int x, int[] arr) {
 // 如果集合i的父亲是自己，说明自己就是源头，返回自己的标号
 if (arr[x] == -1)
 return x;
 else // 否则查找集合i的父亲的源头
 return findRoot(arr[x], arr);
 }

若需要在查找过程中添加路径压缩的优化，我们修改上面这个函数为：

 // 并查集查找根节点（优化算法,本质是将路径压缩了）
 static int findRootUseful(int x, int[] arr) {
 int res = 0;
 if (arr[x] == -1)
 return x;
 else {
 res = findRoot(arr[x], arr);
 arr[x] = res; // 将当前结点的双亲结点设置为查找返回的根结点编号
 return res;
 }
 }

合并

上面的图片就是关于合并的解法，至于怎么合并就是要看题目的要求了，详见代码示例中的注释

 //set1表示x所在的集合，set2表示y所在的集合
 // 合并两个集合,至于按照什么原则合并就要按照题目意思了，在这里我定义了两个变量，用以比较set1和set2的某种属性之间的差异
 //如果rankX>rankY,就需要把y的集合合并到x的根节点下，也就是set2[y]=x，否则就是将x的集合放到y的根节点下，即set1[x]=y
 static int rankX = 0;
 static int rankY = 1;
 static void union(int x, int y, int[] set1, int[] set2) {
 x = findRootUseful(x, set1);
 y = findRootUseful(y, set2);
 if (x == y)
 return;
 else if (rankX > rankY) {
 set2[y] = x;
 } else {
 if (rankX == rankY)
 rankY++;
 set1[x] = y;
 }
 }

閱讀更多 僱個城管打天下y 的文章

關鍵字: 数据结构 查集 集合