并查集路径压缩(Java 实例代码)
目录
并查集路径压缩
Java 实例代码
UnionFind3.java 文件代码:
并查集路径压缩
并查集里的 find 函数里可以进行路径压缩,是为了更快速的查找一个点的根节点。对于一个集合树来说,它的根节点下面可以依附着许多的节点,因此,我们可以尝试在 find 的过程中,从底向上,如果此时访问的节点不是根节点的话,那么我们可以把这个节点尽量的往上挪一挪,减少数的层数,这个过程就叫做路径压缩。
如下图中,find(4) 的过程就可以路径压缩,让数的层数更少。

节点 4 往上寻找根节点时,压缩第一步,树的层数就减少了一层:

节点 2 向上寻找,也不是根节点,那么把元素 2 指向原来父节点的父节点,操后后树的层数相应减少了一层,同时返回根节点 0。

find 过程代码修改为 :
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find(int p){
assert( p >= 0 && p < count );
// path compression 1
while( p != parent[p] ){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
上述路径压缩并不是最优的方式,我们可以把最初的树压缩成下图所示,层数是最少的。

这个 find 过程代表表示为:
...
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find(int p) {
assert (p >= 0 && p < count);
//第二种路径压缩算法
if (p != parent[p])
parent[p] = find(parent[p]);
return parent[p];
}
...
Java 实例代码
源码包下载:Download
UnionFind3.java 文件代码:
package runoob.union;
/**
* 基于rank的优化
*/
public class UnionFind4 {
private int[] rank; // rank[i]表示以i为根的集合所表示的树的层数
private int[] parent; // parent[i]表示第i个元素所指向的父节点
private int count; // 数据个数
// 构造函数
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find(int p){
assert( p >= 0 && p < count );
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
//第二种路径压缩算法
//if( p != parent[p] )
//parent[p] = find( parent[p] );
//return parent[p];
}
// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
if( rank[pRoot] < rank[qRoot] ){
parent[pRoot] = qRoot;
}
else if( rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // 维护rank的值
}
}
}
相关文章:
并查集路径压缩(Java 实例代码)
目录 并查集路径压缩 Java 实例代码 UnionFind3.java 文件代码: 并查集路径压缩 并查集里的 find 函数里可以进行路径压缩,是为了更快速的查找一个点的根节点。对于一个集合树来说,它的根节点下面可以依附着许多的节点,因此&am…...
Educational Codeforces Round 153 (Rated for Div. 2)
A.我直接构造((())))和()()()这种了,因为这两种都很简便,只有()和…...
分布式 | 如何搭建 DBLE 的 JVM 指标监控系统
本篇文章采用 Docker 方式搭建 Grafana Prometheus 实现对 DBLE 的 JVM 相关指标的监控系统。 作者:文韵涵 爱可生 DBLE 团队开发成员,主要负责 DBLE 需求开发,故障排查和社区问题解答。 本文来源:原创投稿 爱可生开源社区出品&a…...
下线40万辆,欧拉汽车推出2023款好猫尊荣型和GT木兰版
欧拉汽车是中国新能源汽车制造商,成立于2018年。截至目前,已经下线了40万辆整车,可见其在市场的影响力和生产实力。为了庆祝这一里程碑,欧拉汽车推出了品牌书《欧拉将爱进行到底》,在其中讲述了欧拉汽车的发展历程和未…...
【Python】使用python解析someip报文,以someip格式打印报文
文章目录 1.安装scapy库2.解析someip格式报文3.示例 1.安装scapy库 使用 pip 安装 scapy 第三方库,打开 cmd,输入以下命令: pip install scapy出现如图所示,表示安装成功: 2.解析someip格式报文 要解析someip格式报…...
C#与西门子PLC1500的ModbusTcp服务器通信2--ModbusTcp协议
Modbus TCP是近年来越来越流行的工业控制系统通信协议之一,与其他通信协议相比,Modbus TCP通信速度快、可靠性高、兼容性强、适用于模拟或数字量信号的传输,阅读本文前你必须比较熟悉Modbus协议,了解tcp网络。 一、什么是Modbus …...
SpringBoot + MyBatis-Plus构建树形结构的几种方式
1. 树形结构 树形结构,是指:数据元素之间的关系像一颗树的数据结构。由树根延伸出多个树杈 它具有以下特点: 每个节点都只有有限个子节点或无子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点&a…...
linux vscode 下开发
linux vscode 下开发 javajdk插件查看调用层次 java jdk 各种JAVA JDK的镜像分发 编程宝库 - 技术改变世界 jdk 镜像 ubuntu22.04 安装 # Linux x64 64位 jdk-8u351-linux-x64.tar.gztar -zxf jdk-8u351-linux-x64.tar.gz mv jdk1.8.0_351 jdk8/ vim ~/.pr…...
【工具】python代码编辑器--PyCharm下载安装和介绍
PyCharm是一种Python IDE(集成开发环境),由JetBrains打造。它带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具,比如调试、语法高亮、项目管理、代码跳转、智能提示、自动完成、单元测试、版本控制等。此外,PyCharm还提供了一些高级功能,以用于支持Django框…...
SpringBoot第44讲:SpringBoot集成Redis - Redis分布式锁的实现之Jedis(setNXPX+Lua)
SpringBoot第44讲:SpringBoot集成Redis - Redis分布式锁的实现之Jedis(setNXPXLua) Redis实际使用场景最为常用的还有通过Redis实现分布式锁。本文是SpringBoot第44讲,主要介绍Redis实现分布式锁 文章目录 SpringBoot第44讲:SpringBoot集成Re…...
STM32F4X USART串口使用
STM32F4X USART串口使用 串口概念起始位波特率数据位停止位校验位串口间接线 STM32F4串口使用步骤GPIO引脚复用函数串口初始化函数串口例程 串口概念 串口是MCU与外部通信的重要通信接口,也是MCU在开发过程中的调试利器。串口通信有几个重要的参数,分别…...
python实现两个字符串比对差异点
一:代码实现 import difflib, re# 比较两个文本差异点 def compare_text_index(text1, text2):# 创建SequenceMatcher对象matcher = difflib.SequenceMatcher(a=text1, b=text2)# 获取差异报告diff_report = matcher.get_opcodes()# 检查差异报告中是否存在关键词错误for tag…...
SQLite数据库实现数据增删改查
当前文章介绍的设计的主要功能是利用 SQLite 数据库实现宠物投喂器上传数据的存储,并且支持数据的增删改查操作。其中,宠物投喂器上传的数据包括投喂间隔时间、水温、剩余重量等参数。 实现功能: 创建 SQLite 数据库表,用于存储宠…...
【Golang系统开发】搜索引擎(2) 压缩词典
写在前面 这篇文章我们就给出一系列的数据结构,使得词典能达到越来越高的压缩比。当然,和倒排索引记录表的大小相比,词典只占据了非常小的空间。那么为什么要对词典进行压缩呢? 这是因为决定信息检索系统的查询响应时间的一个重…...
clickhouse修改默认密码
1.明文密码 vim /etc/clickhouse-server/users.xml找到下面的语句,增加明文密码 <password>123456789</password> 2. sha256密码 # echo -n 123456789 | openssl dgst -sha256 (stdin) 15e2b0d3c33891ebb0f1ef609ec419420c20e320ce94c65fbc8c3312448eb225 修改…...
基于java在线捐赠系统设计与实现
摘要 近年来,随着网络的快速发展,由于网络的开放性和便利性,具有广阔的发展前景。 本文设计并实现了医药捐赠系统。通过分析确定由两个不同的用户组成,每个用户具有不同的功能。它还可以帮助用户在线求助、申请项目、发表留言等&a…...
【前端】vscode javascript 代码片段失效问题解决
1. 文件--首选项--用户代码片段-vue.json : 添加 // { // // Place your global snippets here. Each snippet is defined under a snippet name and has a scope, prefix, body and // // description. Add comma separated ids of the languages where the snippet is app…...
AE-卡通人物解说动画视频的制作
目录 1.导入卡通人物图片和音频文件 2.新建合成 3.在卡通人物图片上添加效果和表达式 4.在音频文件上添加效果和表达式 5.将卡通人物中的 CC Split2 中分割1 表达式链接到滑块中 6.卡通人物根据音频文件自动匹配口型。 AE制作卡通人物解说视频,卡通人物口型根据…...
Linux 查看日志
在 Linux 中,内核日志使用 printk 函数进行输出。你可以通过以下方法查看 printk 的日志: 使用 dmesg 命令: dmesg 这个命令会显示内核环缓冲区中的日志消息,包括使用 printk 输出的消息。你可以通过滚动浏览输出来查看完整的日志…...
使用IO多路复用select完成TCP循环服务器接收客户端消息并打印
服务器 客户端 结果...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
