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

并查集

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