[算法系列之二十八]并查集（不相交集合）

墨蓝 2023-06-23 02:55 15阅读 0赞

**一 概述**

并查集（Disjoint set或者Union-find set）是一种树型的数据结构，常用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构：

> 1.  Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
> 2.  Union：将两个子集合并成同一个集合。

因为它支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于建立单元素集合。有了这些方法，许多经典的划分问题可以被解决。

为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着。Find（x）返回x所属集合的代表，而Union（x，y）使用两个集合的代表x，y作为参数。

**二 主要操作**

> 1.  1.MakeSet（x）
> 2.  2.Find（x）
> 3.  3.Union（x,y）

** 2.1 MakeSet（x） 建立一个新的集合**

建立一个新的集合，其唯一成员（因为是其代表）就是x。因为集合是不相交的，故要求x没有在其它集合中出现过。

**2.2 Find（x） 包含x集合的代表**

返回一个指针，指向包含x的（唯一）集合的代表。

**2.3 Union（x，y） 合并两个不相交集合**

将包含x和y的动态集合合并成为一个新的集合。所得集合的代表可以是两个集合的任何成员。但在很多情况下，我们一般选择两个集合之前代表中的一个作为新的代表。

**三 不相交集合森林（有根树表示集合）**

不相交集合可以用链表实现，但是还有一种更快的方法—–有根树表示集合，树中的每个节点都包含集合的一个成员，每棵树都表示一个集合。如下图：

![20150314212114475][]

左边的树表示集合｛b，c，e，h｝其c是代表；右边的树表示集合｛d，f，g｝其f是代表。

**3.1 MakeSet（x）**

MakeSet创建一棵仅包含一个节点的树。初始时父节点为自己。

#define N 100
    
    //申请内存的大小
    int parent[N];
    
    // parent[x]表示x的父节点
    void MakeSet(int x){
        parent[x] = x;
    }

**3.2 Find（x）**

Find（x）指向包含x的（唯一）集合的代表。沿着父节点指针一直找下去，直到找到树根为止。
    
    int Find(int x){
        // 根节点即集合代表
        if(x == parent[x]){
            return x;
        }//if
        // 沿着父节点指针寻找
        Find(parent[x]);
    }

**3.3 Union（x，y）**

Union操作使的一棵树的根指向另一棵树的根。如下图：

![20150314222350422][]

// 合并
    void Union(int x,int y){
        x = Find(x);
        y = Find(y);
        parent[y] = x;
    }

**四 优化**

**4.1 按秩合并**

其思想是使包含较少结点的树指向包含较多结点的树的根。我们并不显示的记录以每个结点为根的子树的大小，而是采用一种能够简化分析的方法。对每个结点，我们用秩表示结点高度（从该结点到某一后代叶节点的最长路径上边的数目）的一个上界。在按秩合并中，具有较小秩的根在Union操作中指向较大秩的根。

rank\[x\]表示x节点的秩。当由MakeSet创建了一个集合时，对应的树中唯一节点的初始秩为0，每个Find操作都不改变任何秩。

// parent[x]表示x的父节点 rank[x] 表示x的秩
    void MakeSet(int x){
        parent[x] = x;
        rank[x] = 0;
    }

当对两棵树应用Union时，有两种情况：   
（1） 当两个秩不相等时，我们使具有较高秩的根称为具有较小秩的根的父节点，但秩本身保持不变。   
（2）当两个秩相等时，任选一个根作为父节点，并增加其秩的值。

void Union(int x, int y){
        x = Find(x);
        y = Find(y);
        if(x == y) {
            return;
        }//if
        if(rank[x] > rank[y]){
            parent[y] = x;
        }//if
        else if(rank[x] < rank[y]){
            parent[x] = y;
        }//else
        else{
            rank[x]++;
        }//else
    }

**4.2 路径压缩**

寻找祖先时，我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find(x)都是O(n)的复杂度。为了避免这种情况，我们需对路径进行压缩，即当我们经过”递推”找到祖先节点后，”回溯”的时候顺便将它的子孙节点都直接指向祖先，这样以后再次Find(x)时复杂度就变成O(1)了，如下图所示。可见，路径压缩方便了以后的查找。

其中三角表示子树，其根为所示节点。

// 带路径压缩的Find
    int Find(int x){
        // 根节点即集合代表
        if(x != parent[x]){
            // 更新节点x使之指向根
            parent[x] = Find(parent[x]);
        }//if
        return parent[x];
    }

Find是一种两趟方法：一趟是沿查找路径上升，直到找到根；另一趟是沿查找路径下降，一便更新每个节点，使之指向根节点。

**五 复杂度分析**

空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，N次合并M查找的时间复杂度为O(M Alpha(N))，这里Alpha是Ackerman函数的某个反函数，在很大的范围内（人类目前观测到的宇宙范围估算有10的80次方个原子，这小于前面所说的范围）这个函数的值可以看成是不大于4的，所以并查集的操作可以看作是与m成线性关系。

**六 应用**

并查集常作为另一种复杂的数据结构或者算法的存储结构。常见的应用有：求无向图的连通分量个数，最近公共祖先（LCA），带限制的作业排序，实现Kruskar算法求最小生成树等。

**七 引用**

[并查集 ][Link 1]  
[数据结构之并查集 ][Link 2]  
算法导论

本文原文地址：[https://blog.csdn.net/SunnyYoona/article/details/44264347][https_blog.csdn.net_SunnyYoona_article_details_44264347]

[20150314212114475]: https://img-blog.csdn.net/20150314212114475
[20150314222350422]: https://img-blog.csdn.net/20150314222350422
[Link 1]: http://www.nocow.cn/index.php/%E5%B9%B6%E6%9F%A5%E9%9B%86
[Link 2]: http://dongxicheng.org/structure/union-find-set/
[https_blog.csdn.net_SunnyYoona_article_details_44264347]: https://blog.csdn.net/SunnyYoona/article/details/44264347