C++并查集怎么实现
导读:本文共1712字符,通常情况下阅读需要6分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 并查集 是一种树型的数据结构,用于处理一些不相加集合的合并和查询问题。在使用中常常以森林来表示。 并查集也是用来维护集合的,和前面学习的set不同之处在于,并查集能很方便地同时维护很多集合。如果用set来维护会非常的麻烦。并查集的核心思想是记录每个结点的父亲结点是哪个结点。前言并查集是一种多叉树,用于处理不相交的集合的合并与查询问题(判断)。通俗理解:在日常生活... ...
目录
(为您整理了一些要点),点击可以直达。并查集 是一种树型的数据结构,用于处理一些不相加集合的合并和查询问题。在使用中常常以森林来表示。 并查集也是用来维护集合的,和前面学习的set不同之处在于,并查集能很方便地同时维护很多集合。如果用set来维护会非常的麻烦。并查集的核心思想是记录每个结点的父亲结点是哪个结点。
前言
并查集是一种多叉树,用于处理不相交的集合的合并与查询问题(判断)。
通俗理解:在日常生活中,我们会因为某个人是自己的朋友,哪怕是朋友的朋友也是有朋友,会给予通融、 偏袒。而并查集的基本概念,就是判断某两个集合是否是“朋友”关系,并让两个集合成为“朋友”
常用操作
初始化:每个结点单独作为一个集合
查询:求元素所在的集合的代表元素,即根结点
合并:将两个元素所在的集合,合并为一个集合
合并之前,应先判断两个元素是否属于同一集合,用上面的“查询”来实现
算法实现
初始化:初始的时候每个结点各自为一个集合,father[i]表示结点 i 的父亲结点,如果 father[i]=i,我们认为这个结点是当前集合根结点(开始时每个节点根节点是他自己)。
voidinit(){for(inti=1;i<=n;++i){father[i]=i;}}
查找:查找结点所在集合的根结点,结点 x 的根结点必然也是其父亲结点的根结点(像是有递归的样子)。
intget(intx){if(father[x]==x){//x结点就是根结点returnx;}returnget(father[x]);//如果该节点不是根节点,继续寻找父结点的根结点}
合并:将两个元素所在的集合合并在一起,通常来说,合并之前先判断两个元素是否属于同一集合。
voidhebing(intx,inty){x=find(x);y=find(y);if(x!=y){//不在同一个集合father[y]=x;//将根节点合并}}
上面三个操作是并查集常用的操作
前面的并查集的复杂度实际上在有些极端情况会很慢。比如树的结构正好是一条链,那么最坏情况下,每次查询的复杂度达到了O(n) 。这并不是我们期望的结果。路径压缩的思想是,我们只关心每个结点的父结点,而并不太关心树的真正的结构(递归查找相当浪费时间)如下:
当想去访问6的根节点时,要访问5的根节点,想去访问5的根节点,又要去访问4的根节点..........以此类推,此时并查集退化为线性。
这样我们在一次查询的时候,可以把查询路径上的所有结点的father[i]都赋值成为根结点。只需要在我们之前的查询函数上面进行很小的改动
intfindf(intk){if(f[k]==k)returnk;returnf[k]=findf(f[k]);//后来更新的点的根节点直接为最开始的点,一步找到总根节点。}
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
C++并查集怎么实现的详细内容,希望对您有所帮助,信息来源于网络。