欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-22 16:05:52
...

并查集

  • 在解决卡片问题的时候,我用到的就是并查集来解决,当时就仅仅说了怎么用来,这里我想详细的来学习一下这种数据结构,分析一下这种数据结构的优缺点和应用场合。
  • 实际问题中,我们经常遇到一些将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),这个性能是让我们非常开心的。至于这个复杂度怎么来的,我也尝试着想把它看懂,但是太难后来放弃了,想真正搞算法的还是需要将其看懂。

上一篇: 开源协议

下一篇: 详解并查集