Java并查集设计以及路径压缩实现

Java全能学习+面试指南：https://javaxiaobear.cn

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

  • 查询元素p和元素q是否属于同一组
  • 合并元素p和元素q所在的组

1、并查集的结构

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

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

2、并查集的API设计与实现

1、API设计

类名UnionFind
构造方法UF(int N)：初始化并查集，以整数标识(0,N-1)个结点
成员方法public int count()：获取当前并查集中的数据有多少个分组
public boolean connected(int p,int q):判断并查集中元素p和元素q是否在同一分组中
public int find(int p):元素p所在分组的标识符
public void union(int p,int q)：把p元素所在分组和q元素所在分组合并
成员变量private int[] eleAndGroup: 记录结点元素和该元素所在分组的标识
private int count：记录并查集中数据的分组个数

2、实现

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、代码实现
public class UnionFind {/*** 记录结点元素和该元素所在分组的标识*/private int[] eleAndGroup;/*** 记录并查集中数据的分组个数*/private int count;public UnionFind(int n) {//初始情况下，每个元素都在一个独立的分组中，所以，初始情况下，并查集中的数据默认分为N个组this.count = n;//初始化数组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 eleAndGroup[p] == eleAndGroup[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){//如果q和p已经在同一个分组中，不需要合并if(connected(p, q)){return;}//不在一个分组中int pFind = find(p);int qFind = find(q);for (int i = 0; i < eleAndGroup.length; i++) {if (eleAndGroup[i] == pFind){eleAndGroup[i] = qFind;}}//数量减1count--;}
}

  • 测试类

    public class UnionFindTest {public static void main(String[] args) {UnionFind uf = new UnionFind(5);int count = uf.count();System.out.println("总共有"+count+"个分组");Scanner scanner = new Scanner(System.in);while (true){System.out.println("请输入你要合并的第一个点");int i = scanner.nextInt();System.out.println("请输入你要合并的第二个点");int j = scanner.nextInt();if(uf.connected(i,j)){System.out.println("结点"+ i +"和结点"+ j +"已经在同一个组");continue;}uf.union(i,j);System.out.println("总共还有"+uf.count()+"个分组");}}
}

3、并查集应用举例

如果我们并查集存储的每一个整数表示的是一个大型计算机网络中的计算机，则我们就可以通过connected(intp,int q)来检测，该网络中的某两台计算机之间是否连通？如果连通，则他们之间可以通信，如果不连通，则不能通信，此时我们又可以调用union(int p,int q)使得p和q之间连通，这样两台计算机之间就可以通信了。

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

4、算法优化

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

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

1、API设计

类名UF_Tree
构造方法UF_Tree(int N)：初始化并查集，以整数标识(0,N-1)个结点
成员方法public int count()：获取当前并查集中的数据有多少个分组
public boolean connected(int p,int q):判断并查集中元素p和元素q是否在同一分组中
public int find(int p):元素p所在分组的标识符
public void union(int p,int q)：把p元素所在分组和q元素所在分组合并
成员变量private int[] eleAndGroup: 记录结点元素和该元素的父结点
private int count：记录并查集中数据的分组个数

2、实现

1、find(int p)查询方法实现
  1. 判断当前元素p的父结点eleAndGroup[p]是不是自己，如果是自己则证明已经是根结点了；
  2. 如果当前元素p的父结点不是自己，则让p=eleAndGroup[p]，继续找父结点的父结点,直到找到根结点为止；
2、union(int p,int q)合并方法实现
  1. 找到p元素所在树的根结点
  2. 找到q元素所在树的根结点
  3. 如果p和q已经在同一个树中，则无需合并；
  4. 如果p和q不在同一个分组，则只需要将p元素所在树根结点的父结点设置为q元素的根结点即可；
  5. 分组数量-1

3、完成代码

public class UF_Tree {/*** 记录结点元素和该元素所在分组的标识*/private int[] eleAndGroup;/*** 记录并查集中数据的分组个数*/private int count;public UF_Tree(int n) {//初始情况下，每个元素都在一个独立的分组中，所以，初始情况下，并查集中的数据默认分为N个组this.count = n;//初始化数组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 eleAndGroup[p] == eleAndGroup[q];}/*** 元素p所在分组的标识符* @param p* @return*/public int find(int p){while (true){//判断当前元素p的父结点eleAndGroup[p]是不是自己，如果是自己则证明已经是根结点了；if(p == eleAndGroup[p]){return p;}//如果当前元素p的父结点不是自己，则让p=eleAndGroup[p]，继续找父结点的父结点,直到找到根结点为止；p = eleAndGroup[p];}}/*** 把p元素所在分组和q元素所在分组合并* @param p* @param q*/public void union(int p,int q){//不在一个分组中int pFind = find(p);int qFind = find(q);if (qFind == pFind){return;}//如果p和q不在同一个分组，则只需要将p元素所在树根结点的父结点设置为q元素的根结点即可；eleAndGroup[pFind] = qFind;//数量减1count--;}
}

  • 测试类

    public class UnionFindTreeTest {public static void main(String[] args) {UF_Tree uf = new UF_Tree(5);int count = uf.count();System.out.println("总共有"+count+"个分组");Scanner scanner = new Scanner(System.in);while (true){System.out.println("请输入你要合并的第一个点");int i = scanner.nextInt();System.out.println("请输入你要合并的第二个点");int j = scanner.nextInt();if(uf.connected(i,j)){System.out.println("结点"+ i +"和结点"+ j +"已经在同一个组");continue;}uf.union(i,j);System.out.println("总共还有"+uf.count()+"个分组");}}
}

5、路径压缩

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

之前我们在union算法中，合并树的时候将任意的一棵树连接到了另外一棵树，这种合并方法是比较暴力的，如果我们把并查集中每一棵树的大小记录下来，然后在每次合并树的时候，把较小的树连接到较大的树上，就可以减小树的深度。

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

1、API设计

类名UF_Tree_Weighted
构造方法UF_Tree_Weighted(int N)：初始化并查集，以整数标识(0,N-1)个结点
成员方法public int count()：获取当前并查集中的数据有多少个分组
public boolean connected(int p,int q):判断并查集中元素p和元素q是否在同一分组中
public int find(int p):元素p所在分组的标识符
public void union(int p,int q)：把p元素所在分组和q元素所在分组合并
成员变量private int[] eleAndGroup: 记录结点元素和该元素的父结点
private int[] sz: 存储每个根结点对应的树中元素的个数
private int count：记录并查集中数据的分组个数

2、实现

public class UFTreeWeighted {private int[] eleAndGroup;private int[] rootSize;private int count;public UFTreeWeighted(int count) {this.count = count;//初始化数组eleAndGroup = new int[count];rootSize = new int[count];/*** 把eleAndGroup数组的索引看做是每个结点存储的元素，* 把eleAndGroup数组每个索引处的值看做是该结点所在的分组，* 那么初始化情况下，i索引处存储的值就是i*/for (int i = 0; i < count; i++) {eleAndGroup[i] = i;}//把sz数组中所有的元素初始化为1，默认情况下，每个结点都是一个独立的树，每个树中只有一个元素for (int i = 0; i < count; i++) {rootSize[i] = 1;}}/*** 获取当前并查集中的数据有多少个分组* @return count*/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){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;}//不在一个组中，比较q所在树中的元素个数和p所在树中的元素个数，小树向大树合并if(rootSize[pRoot] < rootSize[qRoot]){eleAndGroup[pRoot] = qRoot;rootSize[qRoot] += rootSize[pRoot];}else {eleAndGroup[qRoot] = pRoot;rootSize[pRoot] += rootSize[qRoot];}//分组数组-1count--;}
}

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/237086.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Unity C# 枚举多选

Unity C# 枚举多选

枚举多选 &#x1f96a;例子&#x1f354;判断 &#x1f96a;例子 [System.Flags]public enum TestEnum{ None 0,Rooms 1 << 1,Walls1<<2,Objects1<<3,Slabs 1 << 4,All Rooms|Walls|Objects|Slabs}&#x1f354;判断 TestEnum test TestEnum.R…
阅读更多...
C++ 手写堆 || 堆模版题：堆排序

C++ 手写堆 || 堆模版题：堆排序

输入一个长度为 n 的整数数列&#xff0c;从小到大输出前 m 小的数。 输入格式 第一行包含整数 n 和 m 。 第二行包含 n 个整数&#xff0c;表示整数数列。 输出格式 共一行&#xff0c;包含 m 个整数&#xff0c;表示整数数列中前 m 小的数。 数据范围 1≤m≤n≤105 &…
阅读更多...
linux（ubuntu）中crontab定时器命令详解 以及windows中定时器

linux（ubuntu）中crontab定时器命令详解 以及windows中定时器

linux&#xff08;ubuntu&#xff09;中crontab定时器命令详解 crontab 是一个用于创建、编辑和管理用户的定时任务的命令&#xff0c;它可以让用户在指定的时间自动执行指定的命令或脚本。 基本语法 -e&#xff1a;编辑用户的 crontab 文件&#xff1b;-l&#xff1a;列出用…
阅读更多...
MySQL的导入导出及备份

MySQL的导入导出及备份

一.准备导入之前 二.navicat导入导出 ​编辑 三.MySQLdump命令导入导出 四.load data file命令的导入导出 五.远程备份 六. 思维导图 一.准备导入之前 需要注意&#xff1a; 在导出和导入之前&#xff0c;确保你有足够的权限。在进行导入操作之前&#xff0c;确保目标数据…
阅读更多...
有了 Prisma，就别用 TypeORM 了

有了 Prisma，就别用 TypeORM 了

要说2024 年 Node.js 的 ORM 框架应该选择哪个&#xff1f;毫无疑问选 Prisma。至于为何&#xff0c;请听我细细道来。 本文面向的对象是饱受 TypeORM 折磨的资深用户(说的便是我自己)。只对这两个 ORM 框架从开发体验上进行对比&#xff0c;你也可以到 这里 查看 Prisma 官方对…
阅读更多...
安装nvidia driver出现 the cc vision check falied

安装nvidia driver出现 the cc vision check falied

这里提示说的需要gcc12,但是我只有gcc11,所以就报错了&#xff0c;说一说我自己的解决方法&#xff1a; 安装gcc12和g12,再切换版本为gcc12 安装gcc12: sudo apt install gcc-12安装g12: sudo apt -y install g-12切换版本&#xff1a;参考博客
阅读更多...
R语言【paleobioDB】——pbdb_map()：根据化石记录绘制地图

R语言【paleobioDB】——pbdb_map()：根据化石记录绘制地图

Package paleobioDB version 0.7.0 paleobioDB 包在2020年已经停止更新&#xff0c;该包依赖PBDB v1 API。 可以选择在Index of /src/contrib/Archive/paleobioDB (r-project.org)下载安装包后&#xff0c;执行本地安装。 Usage pbdb_map (data, col.int"white" ,p…
阅读更多...
如何使用PR制作抖音视频？抖音短视频创作素材剪辑模板PR项目工程文件

如何使用PR制作抖音视频？抖音短视频创作素材剪辑模板PR项目工程文件

如何使用PR软件制作抖音视频作品&#xff1f;Premiere Pro 抖音短视频创作素材剪辑模板PR项目工程文件。 3种分辨率&#xff1a;10801920、10801350、10801080。 来自PR模板网&#xff1a;https://prmuban.com/37058.html
阅读更多...
用React给XXL-JOB开发一个新皮肤（二）：目录规划和路由初始化

用React给XXL-JOB开发一个新皮肤（二）：目录规划和路由初始化

目录 一. 简述二. 目录规划三. Vite 配置 3.1. 配置路径别名3.2. 配置 less 四. 页面 4.1. 入口文件4.2. 骨架文件4.3. 普通页面 五. 路由配置六. 预览启动 一. 简述 上一篇文章我们介绍了项目初始化&#xff0c;此篇文章我们会先介绍下当前项目的目录规划&#xff0c;接着对…
阅读更多...
Python 中的字符串分割函数 split() 详解

Python 中的字符串分割函数 split() 详解

更多Python学习内容&#xff1a;ipengtao.com 在 Python 编程中&#xff0c;处理字符串是一项常见的任务。字符串分割是其中的一个常见操作&#xff0c;而 Python 提供了强大的 split() 函数&#xff0c;用于将字符串拆分成多个部分。本文将详细介绍 split() 函数的用法、参数和…
阅读更多...
Openstack组件glance对接swift

Openstack组件glance对接swift

2、glance对接swift &#xff08;1&#xff09;可直接在数据库中查看镜像存放的位置、状态、id等信息 &#xff08;2&#xff09;修改glance-api的配置文件&#xff0c;实现对接swift存储&#xff08;配置文件在/etc/glance/glance-api.conf&#xff0c;建议先拷贝一份&#x…
阅读更多...
黑马python就业课

黑马python就业课

文章目录 初级中级高级初级课程分享 初级 中级 高级 初级课程分享 链接&#xff1a;https://pan.baidu.com/s/1aiJHaThezv_mSI1rnV3d7g 提取码&#xff1a;xdpc
阅读更多...
嵌套的CMake

嵌套的CMake

hehedalinux:~/Linux/multi-v1$ tree . ├── calc │ ├── add.cpp │ ├── CMakeLists.txt │ ├── div.cpp │ ├── mult.cpp │ └── sub.cpp ├── CMakeLists.txt ├── include │ ├── calc.h │ └── sort.h ├── sort │ ├── …
阅读更多...
Mnajora 使用deb包安装软件

Mnajora 使用deb包安装软件

说明 Mnajora 安装deb软件包主要有两种方式 可以使用dpkg 直接安装也可是使用debtap将deb软件包转换成 使用dpkg sudo pacman -S dpkg #安装dpkgsudo dpkg -i ###.deb #使用dpkg安装deb软件包和在ubuntu上是一样的 安装成功 使用debtap debtap是一个用于将.deb包转换为A…
阅读更多...
im6ull学习总结（三-3）freetype

im6ull学习总结（三-3）freetype

1、Freetype简介 FreeType是一个开源的字体渲染引擎&#xff0c;主要用于将字体文件转换为位图或矢量图形&#xff0c;并在屏幕上渲染出高质量的字体。它提供了一组API&#xff0c;使开发者能够在自己的应用程序中使用和呈现字体。 FreeType最初是作为一个独立项目开发的&…
阅读更多...
07-Tomcat运行Jenkins并实现链路追踪

07-Tomcat运行Jenkins并实现链路追踪

4.3.1&#xff1a;部署skywalking java agent ~# apt install openjdk-11-jdk -y ~# cd /apps/ ~# wget https://archive.apache.org/dist/skywalking/java-agent/9.0.0/apache-skywalking-java-agent-9.0.0.tgz ~# tar xf apache-skywalking-java-agent-9.0.0.tgz ~# vim /ap…
阅读更多...
Git的安装

Git的安装

1、下载 官网地址&#xff1a; https://git-scm.com/或https://github.com/git-for-windows/git/releases 百度网盘链接&#xff1a;链接&#xff1a;https://pan.baidu.com/s/13_asGO-XQb5KWWH_V7rq6g?pwd0630 2、安装 ①查看GNU协议&#xff0c;可以直接点击下一步。 ②…
阅读更多...
橘子学Spring01之spring的那些工厂和门面使用

橘子学Spring01之spring的那些工厂和门面使用

一、Spring的工厂体系 我们先来说一下spring的工厂体系(也称之为容器)&#xff0c;得益于大佬们对于单一职责模式的坚决贯彻&#xff0c;在十几年以来spring的发展路上&#xff0c;扩展出来大量的工厂类&#xff0c;每一个工厂类都承担着自己的功能(其实就是有对应的方法实现)…
阅读更多...
Linux 期末复习

Linux 期末复习

Linux 期末复习 计算机历史 硬件基础 1&#xff0c;计算机硬件的五大部件&#xff1a;控制器、运算器、存储器、输入输出设备 2&#xff0c;cpu分为精简指令集(RISC)和复杂指令集(CISC) 3&#xff0c;硬件只认识0和1&#xff0c;最小单位是bit&#xff0c;最小存储单位是字…
阅读更多...
【论文阅读】Non-blocking Lazy Schema Changes in Multi-Version

【论文阅读】Non-blocking Lazy Schema Changes in Multi-Version

Non-blocking Lazy Schema Changes in Multi-Version Database Management Systems 1. Intro 1.1 Motivation 一个是online能够提供不停机的更新的能力&#xff0c;在很多业务系统里面是必要的。第二个是满足高可用&#xff0c;SaaS、PaaS要提供高可用的系统给用户&#xff…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023