数据结构——不相交集(并查集)

news/2024/7/25 2:37:31/文章来源:https://blog.csdn.net/2301_79376014/article/details/139245781

一、基本概念

关系:定义在集合S上的关系指对于a,b∈S,若aRb为真,则a与b相关

等价关系:满足以下三个特性的关系R称为等价关系

(1)对称性,aRb为真则bRa为真;

(2)反身性,aRa为真;

(3)传递性,aRb为真,bRc为真,则aRc为真

等价类:等价类E是集合S的子集,其中E内的任意两个元素构成等价关系

不相交集:将集合S分为若干个等价类,等价类之间不包含相同的元素,对于x∈S,x只属于S中一个等价类。由于子集之间不包含相同的元素,将这样的集合称为不相交集。不相交集中主要基本操作是查找find和合并union,故常称为并查集。find查找给定元素所在的等价类,union将不在同一个等价类中的两个元素归并到一个等价类中,即将两个等价类归并为一个新的等价类。

 二、不相交集的实现

①线性表,线性表的第i个元素保存其所处等价类的名称,find时间复杂度O(1),union时间复杂度O(N)

②采用树状结构,用一棵树表示一个并查集,每个并查集由树根唯一标识,则不相交集就构成一篇森林。判断结点处于哪一个并查集,需寻找其所在树的树根,因此采用双亲表示。在数组s[i]中,s[i]存储结点i的父结点的下标值,根结点则存特殊的-1。find就是向上找直到树根,时间复杂度O(logN),union就是把一棵树作为另一颗树的子树,时间复杂度为O(1)

完成find的时间正比于从结点到根结点的路径长度,最坏的情况是O(N)[树退化为线性结构],而find的性能一定程度上受到union的影响,因为在union过程中不考虑树的结构。改进思想是避免树增高,有两种思路:按规模归并,按高度归并,按高度归并可以保证find时间是对数级别。

 

 最理想的情况是每一棵树的高度为2,只有根结点以及孩子结点,这时find的效率最高,尽管第一个改进能够提高find的效率,但是当两颗树高度接近时还是会使树的高度增加,引入第二个提高效率的方法:在find的时候进行路径压缩,即将路径上所有结点的父结点改为根结点。

 Find(14)   return  parent[14]=Find(12)  0

Find(12)  return  parent[12]=Find(11)  0

Find(11)   return parent[11]=Find(9)  0

Find(9)    return  parent[9]=Find(3)   0

Find(3)  parent[0]=-15<0 return 0

 

三、不相交集的应用

 1.生成迷宫

将迷宫看成是M*N矩阵,每一个小块视为一个元素,左上角为入口,右下角为出口。块与块之间的连通关系属于等价关系,因此迷宫生成可以用并查集来实现。初始时块与块之间由墙分隔,通过随机拆墙的方法,逐渐连通迷宫中的区域,直至入口和出口连通时迷宫形成。

2.最近公共祖先问题

 

采取后序遍历的原因:先遍历两个结点,再遍历到其公共祖先

并查集的作用:每棵子树的根视作等价类的标志,当两个结点同属一棵树即同属一个等价类时,就找到了最近公共祖先。 

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

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

相关文章

【Qt Creator】跨平台的C++图形用户界面应用程序开发框架---QT

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 1.互联网的核心岗位以及职…

3D工业视觉

前言 本文主要介绍3D视觉技术、工业领域的应用、市场格局等&#xff0c;主要技术包括激光三角测量、结构光、ToF、立体视觉。 一、核心内容 3D视觉技术满足工业领域更高精度、更高速度、更柔性化的需求&#xff0c;扩大工业自动化的场景。 2D视觉技术基于物体平面轮廓&#…

JavaScript面试 题

1.延时加载JS有哪些方式 延时加载 :async defer 例如:<script defer type"type/javascript" srcscript.js></ script> defer:等html全部解析完成,才会执行js代码,顺次执行的 async: js和html解析是同步的,不是顺次执行js脚本(谁先加载完先执行谁)2.JS数…

C语言实现Hash Map(3):Map代码优化

在上一节中&#xff0c;我们学习了C语言实现Hash Map(2)&#xff1a;Map代码实现详解&#xff0c;通过代码&#xff0c;我们更深入地了解了Map实现的原理&#xff0c;学习了如何通过key找到对应的桶并加入节点。也正如上一节提到的&#xff0c;虽然这是github中star比较多的代码…

其二:使用递归法实现二分搜索

开篇 本文主要是利用递归法来实现一个简单的二分搜索程序。题目来源是《编程珠玑》第4章课后习题3。 问题概要 编写并验证一个递归的二分搜索程序, 并返回t在数组x[0…n-1]中第一次出现的位置。 思路分析 本题的思路与第一版相似&#xff0c;不过不同的是&#xff0c;为确保返回…

《Python侦探手册:用正则表达式破译文本密码》

在这个信息爆炸的时代&#xff0c;每个人都需要一本侦探手册。阿佑今天将带你深入Python的正则表达式世界&#xff0c;教你如何像侦探一样&#xff0c;用代码破解文本中的每一个谜题。从基础的字符匹配到复杂的数据清洗&#xff0c;每一个技巧都足以让你在文本处理的领域中成为…

c++ 将指针转换为 void* 后,转换为怎么判断原指针类型?

当将指针转换为void后&#xff0c;擦除了指针所指向对象的类型信息&#xff0c;因此无法通过void指针来判断原始指针的类型。我这里有一套编程入门教程&#xff0c;不仅包含了详细的视频讲解&#xff0c;项目实战。如果你渴望学习编程&#xff0c;不妨点个关注&#xff0c;给个…

【C++】Vector的简易模拟与探索

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…

【LeetCode算法】第83题:删除排序链表中的重复元素

目录 一、题目描述 二、初次解答 三、官方解法 四、总结 一、题目描述 二、初次解答 1. 思路&#xff1a;双指针法&#xff0c;只需遍历一遍。使用low指向前面的元素&#xff0c;high用于查找low后面与low不同内容的节点。将具有不同内容的节点链接在low后面&#xff0c;实…

C语言 | Leetcode C语言题解之第116题填充每个节点的下一个右侧节点指针

题目&#xff1a; 题解&#xff1a; struct Node* connect(struct Node* root) {if (root NULL) {return root;}// 从根节点开始struct Node* leftmost root;while (leftmost->left ! NULL) {// 遍历这一层节点组织成的链表&#xff0c;为下一层的节点更新 next 指针stru…

滑动窗口-java

主要通过单调队列来解决滑动窗口问题&#xff0c;得到滑动窗口中元素的最大值和最小值。 目录 前言 一、滑动窗口 二、算法思路 1.滑动窗口 2.算法思路 3.代码详解 三、代码如下 1.代码如下 2.读入数据 3.代码运行结果 总结 前言 主要通过单调队列来解决滑动窗口问题&#xff…

动效设计师的角色与职责:创造视觉魔法!

当今社会&#xff0c;随着视频游戏和数字产品的不断发展&#xff0c;动态设计师这个职业也在逐步发展壮大&#xff0c;同时也吸引了很多热爱动画设计的朋友。动态设计的目的是在第一时间吸引用户的注意力。那你知道动态设计师是做什么的吗&#xff1f;动态设计师的发展前景如何…

微信资源混淆,导致的约束布局 Constraintlayout 控件重叠!

问题 1、广告六要素 虽然我不参与广告 sdk 接入等相关工作&#xff0c;但是最近总是听到一个词广告六要素。这到底是什么&#xff1f; 国内下载类广告&#xff0c;尤其是针对移动应用推广的广告&#xff0c;其成功实施往往围绕几个关键要素进行&#xff0c;这些要素能够帮助…

智研未来,直击 AI DevOps,阿里云用户交流日杭州站来啦!

在这个技术日新月异的时代&#xff0c;云上智能化 DevOps 正以前所未有的速度推动企业创新边界&#xff0c;重塑软件开发的效率与品质。 为深入探索这一变革之路&#xff0c;诚邀您参与我们的专属闭门技术沙龙&#xff0c;携手开启一场关于云上智能化 DevOps 的挑战、实践与未…

展现金融科技前沿力量,ATFX于哥伦比亚金融博览会绽放光彩

不到半个月的时间里&#xff0c;高光时刻再度降临ATFX。而这一次&#xff0c;是ATFX不曾拥有的桂冠—“全球最佳在线经纪商”(Best Global Online Broker)。2024年5月15日至16日&#xff0c;拉丁美洲首屈一指的金融盛会—2024年哥伦比亚金融博览会(Money Expo Colombia 2024) 于…

#12松桑前端后花园周刊-SolidStart、Vercel融资、Angular18、Nextjs15RC、p5.js、ChromeDevTools引入AI

⚡️行业动态 SolidStart 1.0 元框架发布 Solidjs 核心团队发布其元框架 SolidStart 1.0 正式版&#xff0c;其特点如下&#xff1a;基于文件系统的路由&#xff1b;支持SSR、流式SSR、CSR、SSG渲染模式&#xff1b;通过代码分割、树摇和无用代码删除构建优化&#xff1b;基于…

typora自动生成标题序号(修改V1.0)

目录 带序号效果图 解决方法 带序号效果图 解决方法 1.进入文件夹&#xff1a;文件–>偏好设置–>外观–>主题–>打开主题文件夹 2.如果没有base.user.css文件&#xff0c;新建一个。如果有直接用记事本打开&#xff0c;把下面代码拷贝进去保存。 /** initiali…

设计模式 19 模板模式 Template Pattern

设计模式 19 模板模式 Template Pattern 1.定义 模板模式&#xff08;Template Pattern&#xff09;是一种行为设计模式&#xff0c;它定义了一个算法的骨架&#xff0c;将一些步骤的具体实现延迟到子类中。在模板模式中&#xff0c;定义了一个抽象类&#xff0c;其中包含了一个…

什么是光栅化?

一、 什么是光栅化? 光栅化作用是将几何数据变换后转换为像素呈现在显示设备上的一个过程。几何数据转换为像素&#xff0c; 本质是坐标变换、几何离散化&#xff0c;如下&#xff1a; 其中包含了坐标变换和几何离散化&#xff1a; 二、光栅化完成了什么 3D中&#xff0c;物…

Vue2 Element-UI 分页组件el-pagination 修改 自带的total、跳转等默认文字

场景需求&#xff1a; Vue2 Element-UI 分页组件el-pagination 修改 自带的total、跳转等默认文字。如下图&#xff1a;默认提示字变成了英文&#xff0c;如何将其 变成 汉字提示呢&#xff1f; 解决方案&#xff1a; 1.方案1&#xff1a;修改DOM内容 不提倡此方案&#xf…