【数据结构与算法】第十三章：并查集（并查集结构、API设计、代码实现、算法优化、性能分析、路径压缩）

本文主要是介绍【数据结构与算法】第十三章：并查集（并查集结构、API设计、代码实现、算法优化、性能分析、路径压缩），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

并查集是一种树型的数据结构 ，并查集可以高效地进行如下操作：

• 查询 元素p和元素q是否属于同一组

• 合并 元素p和元素q所在的组

13.1、并查集结构

并查集也是一种树型结构，但这棵树跟二叉树、红黑树、B树等都不一样，这种树的要求比较简单：

1. 每个元素都 唯一 的对应一个结点
2. 每一组数据中的多个元素都在 同一颗树 中
3. 一个组中的数据对应的树和另外一个组中的数据对应的 树之间没有任何联系
4. 元素在树中并 没有子父级关系 的硬性要求

13.2、并查集API设计

13.3、并查集实现

1）UF(int N)构造方法

1. 初始情况下，每个元素都在一个独立的分组中，所以，初始情况下，并查集中的数据默认分为N个组
2. 初始化数组eleAndGroup
3. 把eleAndGroup数组的索引看做是每个结点存储的元素，把eleAndGroup数组每个索引处的值看做是该结点所在的分组，那么初始化情况下，i索引处存储的值就是i

2）union(int p,int q)合并方法

1. 如果p和q已经在同一个分组中，则无需合并
2. 如果p和q不在同一个分组，则只需要将p元素所在组的所有元素的组标识符修改为q元素所在组的标识符即可
3. 分组数量-1

3）代码实现

package chapter13;/*** @author 土味儿* Date 2021/9/15* @version 1.0* 并查集*/
public class UnionAndFind {/*** 记录结点元素和该元素所在分组的标识*/private int[] eleAndGroup;/*** 记录并查集中数据的分组个数*/private int count;/*** 构造器** @param n*/public UnionAndFind(int n) {// 初始化分组的数量；默认情况下，有n个分组count = n;// 初始化eleAndGroup分组eleAndGroup = new int[n];// 把eleAndGroup数组的索引看做是每个结点存储的元素，把eleAndGroup数组每个索引处的值看做是该// 结点所在的分组，那么初始化情况下，i索引处存储的值就是ifor (int i = 0; i < n; i++) {eleAndGroup[i] = i;}}/*** 分组的数量** @return*/public int count() {return count;}/*** 判断元素p和q是否在同一个分组中** @param p* @param q* @return*/public boolean connected(int p, int q) {return find(p) == find(q);}/*** 获取元素p所在分组的标识符** @param p* @return*/public int find(int p) {return eleAndGroup[p];}/*** 把元素p合并到q所在的分组** @param p* @param q*/public void union(int p, int q) {// 判断p和q是否在同一个分组if (connected(p, q)) {return;}// p的分组标识符int pGroup = find(p);// q的分组标识符int qGroup = find(q);// 把元素p所在分组中的所有元素标识符，换成q元素所在分组的标识符for (int i = 0; i < eleAndGroup.length; i++) {if (eleAndGroup[i] == pGroup) {eleAndGroup[i] = qGroup;}}// 分组数量减1count--;}
}

    public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入并查集中分组数量：");int n = sc.nextInt();UnionAndFind uf = new UnionAndFind(n);while (true) {System.out.println("请输入第一个要合并的元素：");int p = sc.nextInt();System.out.println("每输入第二个要合并的元素：");int q = sc.nextInt();// 判断p、q是否在同一个分组if (uf.connected(p, q)) {System.out.println(p + "，" + q + "已经在同一个分组了！");continue;}uf.union(p, q);System.out.println("现在分组个数：" + uf.count());}}

每输入第二个要合并的元素：
2
1，2已经在同一个分组了！
请输入第一个要合并的元素：
1
每输入第二个要合并的元素：
3
现在分组个数：3
请输入第一个要合并的元素：
2
每输入第二个要合并的元素：
3
2，3已经在同一个分组了！
请输入第一个要合并的元素：

4）应用举例

如果并查集存储的每一个整数表示的是一个大型计算机网络中的计算机，则就可以通过connected(int p,int q)来检测，该网络中的某两台计算机之间是否连通？

如果连通，则他们之间可以通信，如果不连通，则不能通信，此时又可以调用union(int p,int q)使得p和q之间连通，这样两台计算机之间就可以通信了。

一般像计算机这样网络型的数据，要求网络中的每两个数据之间都是相连通的，也就是说，需要调用很多次union方法，使得网络中所有数据相连，其实很容易可以得出，如果要让网络中的数据都相连，则至少要调用 N-1 次union方法才可以，但由于union方法中使用for循环遍历了所有的元素，所以很明显，之前实现的合并算法的时间复杂度是 O(N^2)，如果要解决大规模问题，它是不合适的，所以需要对算法进行优化

5）UF_Tree算法优化

为了提升union算法的性能，需要重新设计find方法和union方法的实现，此时先需要对之前数据结构中的eleAndGourp数组的含义进行重新设定：

1. 仍然让eleAndGroup数组的索引作为某个结点的元素
2. eleAndGroup[i] 的值不再是当前结点所在的分组标识，而是该结点的 父结点

1、UF_Tree API设计

2、find(int p)查询方法

• 判断当前元素p的父结点eleAndGroup[p]是不是自己，如果是自己则证明已经是根结点了
• 如果当前元素p的父结点不是自己，则让p=eleAndGroup[p]，继续找父结点的父结点,直到找到根结点为止

3、union(int p,int q)合并方法

1. 找到p元素所在树的根结点
2. 找到q元素所在树的根结点
3. 如果p和q已经在同一个树中，则无需合并
4. 如果p和q不在同一个分组，则只需要将p元素所在树根结点的父结点设置为q元素的根结点即可
5. 分组数量-1

4、代码实现

package chapter13;/*** @author 土味儿* Date 2021/9/15* @version 1.0* 并查树*/
public class UFTree {/*** 记录节点元素和该元素的父节点*/private int[] eleAndGroup;/*** 记录并查集中数据的分组个数*/private int count;/*** 构造器** @param n*/public UFTree(int n) {// 初始化分组的数量；默认情况下，有n个分组count = n;// 初始化eleAndGroup分组eleAndGroup = new int[n];// 把eleAndGroup数组的索引看做是每个节点存储的元素，把eleAndGroup数组每个索引处的值看做是该// 节点的父节点，那么初始化情况下，i索引处存储的值就是ifor (int i = 0; i < n; i++) {eleAndGroup[i] = i;}}/*** 分组的数量** @return*/public int count() {return count;}/*** 判断元素p和q是否在同一个分组中** @param p* @param q* @return*/public boolean connected(int p, int q) {return find(p) == find(q);}/*** 获取元素p所在分组的标识符** @param p* @return*/public int find(int p) {// 循环查找while (true){// 判断当前元素p的父节点eleAndGroup[p]是不是自己if(p == eleAndGroup[p]){// 是自己，证明已经是根节点return p;}// 不是自已，从父结点开始继续查找p = eleAndGroup[p];}}/*** 把元素p合并到q所在的分组** @param p* @param q*/public void union(int p, int q) {// p元素所在分组的根节点int pRoot = find(p);// q元素所在分组的根节点int qRoot = find(q);// 判断是否是同一分组if(pRoot == qRoot){return;}// 把p的根节点的父结点设为q的根节点eleAndGroup[pRoot] = qRoot;// 分组数量减1count--;}
}

5、优化后的性能分析

优化后的算法union，如果要把并查集中所有的数据连通，仍然至少要调用N-1次union方法，但是，union方法中已经没有了for循环，所以union算法的时间复杂度由O(N^2)变为了O(N)

但是这个算法仍然有问题，因为之前不仅修改了union算法，还修改了find算法。修改前的find算法的时间复杂度在任何情况下都为O(1)，但修改后的find算法在最坏情况下是 O(N)：

在 union方法中调用了两次find方法，所以在 最坏情况 下union算法的时间复杂度仍然为 O(N^2)

6）路径压缩

UF_Tree中最坏情况下union算法的时间复杂度为O(N^2)，其最主要的问题在于最坏情况下，树的深度和数组的大小一样，如果能够通过一些算法让合并时，生成的树的 深度尽可能的小，就可以优化find方法

之前在union算法中，合并树的时候将任意的一棵树连接到了另外一棵树，这种合并方法是比较暴力的，如果把并查集中每一棵树的大小记录下来，然后在每次合并树的时候，把较小的树连接到较大的树上，就可以减小树的深度
这里说的小树大树指的是树中元素数量，不是树的高度，用另一个数组记录；初始值为1，合并后更新大树的元素数量：原来数量+小树的元素数量

只要保证每次合并，都能把小树合并到大树上，就能够压缩合并后新树的路径，这样就能提高find方法的效率。为了完成这个需求，需要另外一个数组来记录存储每个根节点对应的树中元素的个数，并且需要一些代码调整数组中的值

1、UF_Tree_Weighted API设计

2、代码实现

package chapter13;/*** @author 土味儿* Date 2021/9/15* @version 1.0* 优化并查树* 减小树的高度* 小树合并到大树*/
public class UF_Tree_Weighted {/*** 记录节点元素和该元素的父节点*/private int[] eleAndGroup;/*** 记录并查集中数据的分组个数*/private int count;/*** 记录每个根节点对应的树中元素的数量*/private int sz[];/*** 构造器** @param n*/public UF_Tree_Weighted(int n) {// 初始化分组的数量；默认情况下，有n个分组count = n;// 初始化eleAndGroup分组eleAndGroup = new int[n];// 把eleAndGroup数组的索引看做是每个节点存储的元素，把eleAndGroup数组每个索引处的值看做是该// 节点的父节点，那么初始化情况下，i索引处存储的值就是ifor (int i = 0; i < n; i++) {eleAndGroup[i] = i;}// 初始时每个根结点中元素数量都是1sz = new int[n];for (int i = 0; i < sz.length; i++) {sz[i] = 1;}}/*** 分组的数量** @return*/public int count() {return count;}/*** 判断元素p和q是否在同一个分组中** @param p* @param q* @return*/public boolean connected(int p, int q) {return find(p) == find(q);}/*** 获取元素p所在分组的标识符** @param p* @return*/public int find(int p) {// 循环查找while (true){// 判断当前元素p的父节点eleAndGroup[p]是不是自己if(p == eleAndGroup[p]){// 是自己，证明已经是根节点return p;}// 不是自已，从父结点开始继续查找p = eleAndGroup[p];}}/*** 把元素p合并到q所在的分组** @param p* @param q*/public void union(int p, int q) {// p元素所在分组的根节点int pRoot = find(p);// q元素所在分组的根节点int qRoot = find(q);// 判断是否是同一分组if(pRoot == qRoot){return;}// 比较p、q所在树中元素个数，把小树合并到大树if(sz[pRoot] < sz[qRoot]){// 小树合并到大树eleAndGroup[pRoot] = qRoot;// 更新大树中元素数量：加上小树的数量sz[qRoot] += sz[pRoot];}else{// 小树合并到大树eleAndGroup[qRoot] = pRoot;// 更新大树中元素数量：加上小树的数量sz[pRoot] += sz[qRoot];}// 分组数量减1count--;}
}

7）案例-畅通工程

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）

问最少还需要建设多少条道路？

在测试数据文件夹中有一个trffic_project.txt文件，它就是道路统计表，下面是对数据的解释：

总共有20个城市，目前已经修改好了7条道路，问还需要修建多少条道路，才能让这20个城市之间全部相通？

• 解题思路
  1. 创建一个并查集UF_Tree_Weighted(20)
  2. 分别调用union(0,1)，union(6,9)，union(3,8)，union(5,11)，union(2,12)，union(6,10)，union(4,8)，表示已经修建好的道路把对应的城市连接起来
  3. 如果城市全部连接起来，那么并查集中剩余的分组数目为1，所有的城市都在一个树中，所以，只需要获取当前并查集中剩余的数目，减去1，就是还需要修建的道路数目

package chapter13;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;/*** @author 土味儿* Date 2021/9/15* @version 1.0* 案例：畅通工程*/
public class Traffic_Project {public static void main(String[] args) throws IOException {// 创建缓冲输入流读取BufferedReaderBufferedReader br = new BufferedReader(new InputStreamReader(Traffic_Project.class.getClassLoader().getResourceAsStream("trffic_project.txt")));// 读取第一行数据：城市数量int totalNum = Integer.parseInt(br.readLine());// 构建一个并查集对象UF_Tree_Weighted uf = new UF_Tree_Weighted(totalNum);// 读取第二行数据：已修好的道路数量int roadNum = Integer.parseInt(br.readLine());// 循环读取已经修建好的道路，并调用union方法for (int i = 1;i<=roadNum;i++){String line = br.readLine();String[] str = line.split(" ");int p = Integer.parseInt(str[0]);int q = Integer.parseInt(str[1]);uf.union(p,q);}// 获取剩余的分组数量int need = uf.count();// 计算出还需要修建的道路System.out.println("还需要修建"+(need-1)+"道路，城市才能相通");}
}

还需要修建12道路，城市才能相通

这篇关于【数据结构与算法】第十三章：并查集（并查集结构、API设计、代码实现、算法优化、性能分析、路径压缩）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---