24考研数据结构-并查集
目录
- 5.5.2 并查集(双亲表示法)
- 1. 并查集的存储结构
- 2. 并查集的代码实现
- 初始化
- 并查
- 时间复杂度
- union操作的优化(不要瘦高的树)
- 并查集的进一步优化(find的优化,压缩路径)
- 优化总结
- 数据结构:并查集(Disjoint-Set)
- 并查集的基本操作
- 并查集的实现
- 1. 数组实现并查集
- 2. 普通树结构实现并查集
- 3. 优化的树结构实现并查集
- 原理
- 应用场景
- 代码实现
- 结论
5.5.2 并查集(双亲表示法)
1. 并查集的存储结构


2. 并查集的代码实现
初始化

并查

时间复杂度

union操作的优化(不要瘦高的树)


并查集的进一步优化(find的优化,压缩路径)


优化总结


数据结构:并查集(Disjoint-Set)
在计算机科学中,并查集是一种用于处理集合合并与查询问题的数据结构。它主要用于解决一些实际问题中的集合合并和查询问题,如网络连接问题、社交网络中的好友关系、图论中的连通性问题等。并查集是一种高效的数据结构,能够在常数时间内执行合并和查询操作。
并查集的基本操作
并查集主要包含以下两个基本操作:
-
查找(Find):查找操作用于确定元素所属的集合,即查找元素所在的根节点(代表元素)。如果两个元素的根节点相同,则表示它们属于同一个集合。
-
合并(Union):合并操作用于将两个集合合并为一个集合,即将两个元素所在的集合合并为一个新的集合。合并操作的核心是将其中一个集合的根节点指向另一个集合的根节点,以实现合并。
并查集的实现
并查集可以通过数组和树结构来实现。其中,数组实现是比较简单的方式,但效率相对较低。树结构的实现包括:普通树结构和优化的树结构。
1. 数组实现并查集
数组实现并查集是一种简单而直观的方式,其中每个元素在数组中对应一个父节点。初始时,每个元素的父节点指向自己,表示它们各自构成一个独立的集合。
合并操作可以通过修改数组中某个元素的父节点来实现。例如,将元素A所在的集合合并到元素B所在的集合,只需要将A的父节点指向B即可。
查找操作可以通过递归或循环遍历找到元素所在集合的根节点,直到根节点的父节点指向自己为止。
数组实现并查集的效率相对较低,特别是在查找操作中可能需要较多的遍历操作。
2. 普通树结构实现并查集
普通树结构实现并查集是在数组实现的基础上,将每个集合构造为一棵树结构。合并操作将一个树的根节点链接到另一个树的根节点,从而实现集合的合并。
但是,普通树结构的并查集在处理合并操作时,可能会出现树不平衡的情况,即某个集合的树高度过高,影响了查找操作的效率。
3. 优化的树结构实现并查集
为了优化并查集的性能,在普通树结构的基础上引入了路径压缩和按秩合并两种优化方法。
-
路径压缩:在执行查找操作时,将当前节点到根节点的路径上的所有节点直接链接到根节点,从而减少查找操作中的遍历次数,提高查找效率。
-
按秩合并:在执行合并操作时,将高度较低的树合并到高度较高的树上,从而避免了树的不平衡,提高了合并操作的效率。
优化的树结构实现并查集能够在常数时间内完成合并和查找操作,具有较高的效率和性能。
原理
并查集的基本原理是通过树结构来表示集合,并使用树的根节点来代表集合的代表元素。每个节点表示一个元素,而树的根节点表示该集合的代表元素。在并查集中,每个集合是一棵树,树中的节点通过指针连接。
并查集主要包含两个基本操作:合并和查询。
- 合并操作:将两个不相交的集合合并成一个集合,即将两个树的根节点连接在一起。
- 查询操作:判断两个元素是否属于同一个集合,即判断它们的根节点是否相同。
应用场景
并查集广泛应用于解决具有等价关系的问题,例如:
- 社交网络中的好友关系,判断两个用户是否在同一个社交圈子中。
- 图像处理中的连通区域,判断图像中的像素是否属于同一个区域。
- 岛屿数量问题,判断地图中岛屿的个数和是否相连。
代码实现
在实现并查集时,我们需要定义一个节点结构来表示每个元素,并编写合并和查询操作的函数。
首先,定义一个节点结构:
class Node:def __init__(self, data):self.data = dataself.parent = selfself.rank = 0
在初始化时,每个节点的父节点都是它自己,表示每个节点都是一个单独的集合。rank表示树的高度,用于优化合并操作。
接下来,实现合并和查询操作的函数:
def find(node):if node != node.parent:node.parent = find(node.parent)return node.parentdef union(node1, node2):root1 = find(node1)root2 = find(node2)if root1 == root2:returnif root1.rank > root2.rank:root2.parent = root1elif root1.rank < root2.rank:root1.parent = root2else:root1.parent = root2root2.rank += 1
在find函数中,使用路径压缩来优化查询操作,将节点的父节点直接设为根节点,加快下一次查询的速度。
在union函数中,通过rank来优化合并操作,将高度较低的树连接到高度较高的树上,使得整个树结构更加平衡。
结论
并查集是一种用于处理集合合并与查询问题的高效数据结构。它在解决网络连接、社交网络、图论等问题时具有重要的应用价值。在实际应用中,根据具体的场景和需求,我们可以选择不同的实现方式,如数组实现、普通树结构实现或优化的树结构实现,并根据情况选择合适的优化方法,以获得更高的执行效率和性能。
相关文章:
24考研数据结构-并查集
目录 5.5.2 并查集(双亲表示法)1. 并查集的存储结构2. 并查集的代码实现初始化并查时间复杂度union操作的优化(不要瘦高的树)并查集的进一步优化(find的优化,压缩路径)优化总结 数据结构&#x…...
Redis 和 Mysql 如何保证数据一致性
项目场景: 一般情况下,Redis 用来实现应用和数据库之间读操作的缓存层,主要目的是减少数据库 IO,还可以提升数据的 IO 性能。 如下图所示,这是它的整体架构。 当应用程序需要去读取某个数据的时候,首先会先…...
WSL1升级为WSL2
首先需要启用组件 使用管理员打开Powershell并运行 Enable-WindowsOptionalFeature -Online -FeatureName VirtualMachinePlatform启用后会要求重启计算机 从https://wslstorestorage.blob.core.windows.net/wslblob/wsl_update_x64.msi获取WSL2 Linux内核更新包,…...
力扣 1049. 最后一块石头的重量 II
题目来源:https://leetcode.cn/problems/last-stone-weight-ii/description/ C题解(思路来源代码随想录):本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。 …...
【广州华锐视点】葡萄种植VR虚拟仿真实训平台
随着虚拟现实(VR)技术的不断发展,越来越多的教育领域开始尝试将VR技术应用于教学中。在葡萄栽培这一专业领域,我们开发了一款创新的VR实训课件,旨在为学生提供沉浸式的互动学习体验。本篇文案将为您介绍葡萄种植VR虚拟仿真实训平台所提供的互…...
PBR材质理解整理
PBR Material 草履虫都能看懂的PBR讲解(迫真) 先前看了很多遍类似的了,结合《Unity Shader 入门精要》中的内容整理了下便于以后理解,以后有补充再添加。 光与材质相交会发生散射和吸收,散射改变光的方向,…...
从c++的角度来看ffmpeg 的架构
------------------------------------------------------------------------- author: hjjdebug date: 2023年 08月 01日 星期二 11:26:40 CST descriptor: 从c的角度来看ffmpeg 的架构 ------------------------------------------------------------------------…...
Ubuntu安装JDK与IntelliJ IDEA
目录 前言 Ubuntu 安装 JDK 1、更新软件包列表 2、安装OpenJDK 3、验证安装 Ubuntu安装IntelliJ IDEA 1、下载 IntelliJ IDEA 2、解压缩 IntelliJ IDEA 安装包 3、移动 IntelliJ IDEA 到安装目录 4、启动 IntelliJ IDEA 前言 APT(Advanced Package Tool&…...
【雕爷学编程】Arduino动手做(182)---DRV8833双路电机驱动模块2
37款传感器与执行器的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的&am…...
一个完整的http请求响应过程
一、 HTTP请求和响应步骤 以上完整表示了HTTP请求和响应的7个步骤,下面从TCP/IP协议模型的角度来理解HTTP请求和响应如何传递的。 二、TCP/IP协议 TCP/IP协议模型(Transmission Control Protocol/Internet Protocol),包含了一系…...
Unity通过代码切换材质
效果展示 代码 using System.Collections; using System.Collections.Generic; using UnityEngine;public class MaterialSwitcher : MonoBehaviour {public Material newMaterial; // 新材质private Material oldMaterial; // 旧材质private Renderer renderer; // 渲染器组件…...
Java根据坐标经纬度计算两点距离(5种方法)、校验经纬度是否在圆/多边形区域内的算法推荐
目录 前言 一、根据坐标经纬度计算两点距离(5种方法) 1.方法一 2.方法二 3.方法三 4.方法四 5.方法五 5.1 POM引入第三方依赖 5.2 代码 6.测试结果对比 二、校验经纬度是否在制定区域内 1.判断一个坐标是否在圆形区域内 2.判断一个坐标是否…...
PIC单片机如何设计延时
PIC单片机如何设计延时 PIC单片机的延时基本有两种,一种是自己设计的delay()函数,另一种就是利用其自带的Time定时器。当然一般Time定时器的精度要高于自己设计delay()函数,Time定时器是单片机内部的硬件寄存器模块,而delay()函数是利用自加自减来实现延时,代码进行顺序执…...
FFmpeg常见命令行(二):FFmpeg转封装
前言 在Android音视频开发中,网上知识点过于零碎,自学起来难度非常大,不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》。本文是Android音视频任务列表的其中一个, 对应的要学习的内容是:如何使…...
全面升级:华为鸿蒙HarmonyOS4正式发布,玩趣个性化,小艺AI升级
8月4日新闻,今天下午,华为正式发布了最新版本的鸿蒙操作系统——HarmonyOS 4! 在华为发布会上,鸿蒙HarmonyOS迎来了一系列令人激动的功能升级。其中包括个性化空间、多种生产力工具以及增强的手机AI助手"小艺"。这次更…...
【python】使用Selenium和Chrome WebDriver来获取 【腾讯云 Cloud Studio 实战训练营】中的文章信息
文章目录 前言导入依赖库设置ChromeDriver的路径创建Chrome WebDriver对象打开网页找到结果元素创建一个空列表用于存储数据遍历结果元素并提取数据提取标题、作者、发布时间等信息判断是否为目标文章提取目标文章的描述、阅读数量、点赞数量、评论数量等信息将提取的数据存储为…...
使用Feign 的远程调用,把mysql数据导入es
要把数据库数据导入到elasticsearch中,包括下面几步: 1)将商品微服务中的分页查询商品接口定义为一个FeignClient,放到feign-api模块中 2)搜索服务编写一个测试业务,实现下面功能: 调用item-ser…...
Java课题笔记~ MyBatis接口开发(代理开发)
使用XML文件进行开发,在调用SqlSession进行操作时,需要指定MyBatis映射文件中的方法,这种调用方式过于烦琐。为解决此问题,MyBatis提供了接口开发的方式。 接口开发的目的: 解决原生方式中的硬编码 简化后期执行SQL …...
从数学到深度学习的学习资料及教程合集
诸神缄默不语-个人CSDN博文目录 目前仅收集免费内容,最多需要买本纸质书。 付费的如果有免费版本我也会收录。 链接如失效请联系我。 这个笔记主要是为我自己准备的,算是一个可公开的to do list(其实做不完的我也知道)ÿ…...
nn.CrossEntropyLoss()报错
RuntimeError: “nll_loss_forward_reduce_cuda_kernel_2d_index” not implemented for ‘Float’ Traceback (most recent call last): File "<string>", line 1, in <module> File "/home/zz/anaconda3/envs/torch1.11/lib/python3.7/site-pack…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
