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

2024-04-28 08:38
文章标签 算法 分析 代码 实现 设计 路径 优化 性能 数据结构 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设计、代码实现、算法优化、性能分析、路径压缩）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/942793。

相关文章

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》：本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI
阅读更多...
Python脚本实现自动删除C盘临时文件夹

Python脚本实现自动删除C盘临时文件夹

《Python脚本实现自动删除C盘临时文件夹》在日常使用电脑的过程中,临时文件夹往往会积累大量的无用数据,占用宝贵的磁盘空间,下面我们就来看看Python如何通过脚本实现自动删除C盘临时文件夹吧... 目录一、准备工作二、python脚本编写三、脚本解析四、运行脚本五、案例演示六、注意事项七、总结在日常使用
阅读更多...
Java实现Excel与HTML互转

Java实现Excel与HTML互转

《Java实现Excel与HTML互转》Excel是一种电子表格格式,而HTM则是一种用于创建网页的标记语言,虽然两者在用途上存在差异,但有时我们需要将数据从一种格式转换为另一种格式,下面我们就来看看... Excel是一种电子表格格式，广泛用于数据处理和分析，而HTM则是一种用于创建网页的标记语言。虽然两
阅读更多...
Java中Springboot集成Kafka实现消息发送和接收功能

Java中Springboot集成Kafka实现消息发送和接收功能

《Java中Springboot集成Kafka实现消息发送和接收功能》Kafka是一个高吞吐量的分布式发布-订阅消息系统,主要用于处理大规模数据流,它由生产者、消费者、主题、分区和代理等组件构成,Ka... 目录一、Kafka 简介二、Kafka 功能三、POM依赖四、配置文件五、生产者六、消费者一、Kaf
阅读更多...
使用Python实现在Word中添加或删除超链接

使用Python实现在Word中添加或删除超链接

《使用Python实现在Word中添加或删除超链接》在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能,本文将为大家介绍一下Python如何实现在Word中添加或... 在Word文档中，超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能。通过添加超
阅读更多...
C#使用HttpClient进行Post请求出现超时问题的解决及优化

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧，
阅读更多...
windos server2022里的DFS配置的实现

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS？优势：应用场景：DFS配置步骤什么是DFS？DFS指的是分布式文件系统（Distr
阅读更多...
NFS实现多服务器文件的共享的方法步骤

NFS实现多服务器文件的共享的方法步骤

《NFS实现多服务器文件的共享的方法步骤》NFS允许网络中的计算机之间共享资源,客户端可以透明地读写远端NFS服务器上的文件,本文就来介绍一下NFS实现多服务器文件的共享的方法步骤,感兴趣的可以了解一... 目录一、简介二、部署1、准备1、服务端和客户端：安装nfs-utils2、服务端：创建共享目录3、服
阅读更多...
Java内存泄漏问题的排查、优化与最佳实践

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏？常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏？2.1 使用 J
阅读更多...
C#使用yield关键字实现提升迭代性能与效率

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2