【算法】并查集—带路径压缩的按秩合并法

淩亂°似流年 2022-05-31 02:30 192阅读 0赞

读了《算法导论》的21章：用于不相交集合的数据结构 后在这里对并查集算法做一个小结。  
对于动态集合的表示有多种方法，例如链表和有根树。不论是哪种表示，我们都用一个代表来标识一个集合，这个代表就是该集合中的某个成员。  
并查集算法用于对不相交集合的查找与合并，主要是以下三种操作：

*  **MAKE\_SET(X)**：创建一个新的集合，它包含唯一的成员x（因而为代表）。
 *  **UNION(x,y)**：将分别包含x和y的两个不相交的集合合并为一个新的集合。
 *  **FIND\_SET(x)**：查找x所在的集合，并返回该集合的代表。

《算法导论》介绍了两种实现并查集的方法：链表法和带路径压缩的按秩合并。由于链表法的链表结构相对复杂，个人感觉没有按秩合并简单，所以这里只介绍带路径压缩的按秩合并法。  
带路径压缩的按秩合并法使用有根树来表示集合，树中的每个结点包含一个成员，每个结点仅指向它的父结点，每棵树的根结点包含集合的代表，并且指向自身。如下图a为合并前的两个集合，图b为合并后的集合。  
![这里写图片描述][SouthEast]  
所以我们有以下三种操作：  
**MAKE\_SET**创建一个只有一个结点的树。  
**UNION**将其中一棵树的根结点指向另一棵树的根。  
**FIND\_SET**返回结点所在树的根结点。

为了优化该算法我们还要在引入两种启发性策略：

1.  **按秩合并**：由于我们在找出一个元素所在集合的代表时需要递归地找出它所在的树的根结点，所以为了减短查找路径，在合并两棵树时要尽量使合并后的树的高度降低，所以要将高度低的树指向高度更高的那棵。这里我们引入一个秩的概念：为每一个结点维护一个秩，它表示以该节点为根的树的高度的上界。在做合并操作时，将秩小的根指向秩大的结点。
2.  **路径压缩**：为了进一步减短查找路径，可以使查找路径中的每一个节点都指向根结点，这就是路径压缩。如图  
    ![这里写图片描述][SouthEast 1]

下面给出这三个函数的伪代码

MAKE_SET(x):
        x.p = x;
        x.rank = 0;
    
    //按秩合并
    UNION_SET:
        LINK(FIND_SET(x), FIND_SET(y));
    
    LINK(x,y):
        if(x.rank < y.rank):
            x.p = y;
        else:
            y.p = x;
            if(x.rank == y.rank):
                x.rank = x.rank + 1
    
    //带有路径压缩的查找操作
    FIND_SET:
        if(x.p != x):
            x.p = FIND_SET(x.p);
        return x.p;

[SouthEast]: /images/20220531/1f70bf4a16a64499ac6af7adf997a1fd.png
[SouthEast 1]: /images/20220531/2b0041b462ef45099cdb201483bc1a70.png