不相交集合的数据结构-并查集

xiaoxiao2021-02-28  24

并查集

在解决卡片问题的时候,我用到的就是并查集来解决,当时就仅仅说了怎么用来,这里我想详细的来学习一下这种数据结构,分析一下这种数据结构的优缺点和应用场合。实际问题中,我们经常遇到一些将n个不同的元素根据元素之间的关联将其分成若干个不相交的集合。这些数据结构支持寻找特定的元素和合并两个集合。

1.并查集的一些操作

在介绍操作之前,我得先说说实现这些操作的背景。对于并查集中的每一个集合,都有一个代表,这个代表就是集合中的一个元素,其表示了整个集合。打个比喻吧,最近召开了19大,各个代表都召集到了人民大会堂,假设每个代表都代表着某个省份的人去参加会议,比如我是江西的,江西省的人大代表就代表了江西人民参加会议进行投票,这个代表就代表了整个江西人民这个集合。知道代表这个概念,就可以聊聊并查集的操作了。

MAKE-SET(X):建立一个新的集合,其唯一的成员为x。这里注意,每个集合之间不相交,所以一个元素不可能出现在两个集合中。UNION(x,y):将两个包含x和y的动态集合合并成一个新的集合。FIND-SET(x):返回一个指针,指针指向x集合中的代表 为了更好的分析算法时间复杂度,我们不妨设n为MAKE-SET操作的次数,m为MAKE-SET(X)、UNION(x,y)、FIND-SET(x)操作次数的总和。

下面简述一下并查集的一个简单应用:确定无向图中连通分量

如下所示;

由上可知,集合中包含了各个节点,通过边(u,v)将两个集合进行合并。

并查集和链式结构

在并查集和链式结构中,每个节点由3个属性构成:1、一个元素值2、一个指向对象的指针3、一个指向后一个节点的指针。具体结构图如下所示:在链式结构中,make-set和find-set的时间复杂度分别为O(1),但是union(x,y)的时间复杂度为线性的,因为合并之后,合并后的节点需要更改指向对象的指针。

并查集的改进 我们可以通过一棵有根树结构来对节点进行储存,每个树节点包括一个元素,每棵树代表一个集合,将根节点作为集合的代表。这样的结构通过按秩合并路径压缩两种方法,我们可以对并查集的操作时间复杂度进行优化。下面来介绍一下这两种方法:

按秩合并

简单的来说,按秩合并就是在两个集合合并的时候会出现一个矛盾,两个集合都有一个代表,那么谁来当这个新集合的代表呢??前面的方式是第一个集合的代表作为新集合的代表,这样显然是不合符情理的,所以按秩合并就是,哪颗树的深度越高,树的根节点就作为新树的根节点。换句话说就是哪边元素多,哪边的代表就作为新的代表,这样才是我们想要的。

路径压缩

这种方法的意思就是,在树的结构中,通过元素x来查找根节点肯定会产生一个查找分支,新树合并后,这个分支的每个节点都指向根节点。 上图总a就是我们查找根节点的元素,分支最后都指向更接点。

伪代码

MAKE_SET(x) //构建一个新集合 x.p=x x.rank=0 UNINO(x,y) //合并两个集合 link(FIND-SET(x),FIND-SET(y)) //利用根节点将两个集合合并 LINK(x,y) if x.rank>y.rank //如果x树的深度大于y树的深度 y.p=x //x作为根节点 else x.p=y //如果x树的深度小于等于y的深度,y作为根节点 if(x.rank==y.rank) //如果深度相同时,深度加1 y.rank=y.rank+1 FIND-SET //找到根节点 if x!=x.p //注意这里会实现路径压缩的功能,你按照程序迭代一次就会发现了,这里的伪代码写的也是666 x.p=FIND-SET(x.p) return x.p 上述伪代码,我就不再多加解释了,注释写的很清楚了。我只想分析一下改进后算法的时间复杂度:如果单独采用路径压缩或者按秩合并,都不能直接改变算法的性能。但是两个结合起来,效果就很明显了。如果单独使用按秩合并,时间复杂度为O(mlgn),如果单独使用路径压缩,时间复杂度为,式中f代表FIND-SET操作的数量,如果两者结合,时间复杂度为,其中是一个很小的数,<4,就是说时间复杂度和其操作数的数目成线性,其平均复杂度为常数O(1),这个性能是让我们非常开心的。至于这个复杂度怎么来的,我也尝试着想把它看懂,但是太难后来放弃了,想真正搞算法的还是需要将其看懂。
转载请注明原文地址: https://www.6miu.com/read-1100075.html

最新回复(0)