【数据结构与算法】第十三章：并查集（并查集结构、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。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
性能测试介绍

性能测试介绍

性能测试是一种测试方法，旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试，可以确定系统是否能够满足预期的性能要求，找出性能瓶颈和潜在的问题，并进行优化和调整。 发现性能瓶颈：性能测试可以帮助发现系统的性能瓶颈，即系统在高负载或高并发情况下可能出现的问题
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
hdu1565（状态压缩）

hdu1565（状态压缩）

本人第一道ac的状态压缩dp，这题的数据非常水，很容易过 题意：在n*n的矩阵中选数字使得不存在任意两个数字相邻，求最大值 解题思路： 一、因为在1<<20中有很多状态是无效的，所以第一步是选择有效状态，存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值，状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2