数据结构 | 并查集入门

2019-06-01 本文已影响0人 0与1的邂逅

写在前面：

话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。

这样一来，江湖上就形成了一个一个的群落，通过两两之间的朋友关系串联起来。而不在同一个群落的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？

我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物，这样，每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长，要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？” 这样一来，队长面子上挂不住了，而且效率太低，还有可能陷入无限循环中。

于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通，至于他们是如何连通的，以及每个圈子内部的结构是怎样的，甚至队长是谁，并不重要。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。

——博客：数据结构4——并查集（入门）

并查集

并查集（Union-find Sets）是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。

使用并查集时，首先会存在一组不相交的动态集合 $S = \left\{ {{S_1},{S_2}, \cdots ,{S_k}} \right\}$ ，一般都会使用一个整数表示集合中的一个元素。

每个集合可能包含一个或多个元素，并选出集合中的某个元素作为代表，称为集合的代表元。

每个集合中具体包含了哪些元素是不关心的，具体选择哪个元素作为代表一般也是不关心的。我们关心的是，对于给定的元素，可以很快的找到这个元素所在的集合（的代表），以及合并两个元素所在的集合，而且这些操作的时间复杂度都是常数级的。

并查集的实现原理也比较简单，就是使用树来表示集合，树的每个节点就表示集合中的一个元素，树根对应的元素就是该集合的代表元，如图 1 所示。

图1 并查集的树型表示

图中有两棵树，分别对应两个集合，其中第一个集合为 $\left\{ a, b, c, d \right\}$ ，代表元素是 $a$ ；第二个集合为 $\left\{ e, f, g \right\}$ ，代表元素是 $e$ 。

并查集的基本操作有三个：

makeSet(s)：建立一个新的并查集，其中包含 s 个单元素集合。【初始化】
unionSet(x, y)：把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不相交，如果相交则不合并。【合并】
find(x)：找到元素 x 所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。【查找】

这也就是为什么叫并查集的原因，顾名思义，就是为了进行查和并操作。

【初始化】

树的节点表示集合中的元素，指针表示指向父节点的指针，根节点的指针指向自己，表示其没有父节点。

图2 构造、初始化并查集

#define N 105
int parent[N];// 树型结构的根节点
int r[N];// 树的秩 

//初始化
int init(int n)     //对n个结点初始化
{
    for(int i = 0; i < n; i++)
    {
        parent[i] = i;     // 每个结点的上级都是自己
        r[i] = 0;    // 每个结点构成的树的秩为0
    }
}

【查找】

沿着每个结点的父节点不断向上查找，最终就可以找到该树的根结点，即该集合的代表元素。

int find_parent(int x) // 查找结点x的根结点
{
    if(parent[x] == x) // 递归出口：x的上级为x本身，即x为根结点
    {        
        return x;      
    }
    return find_parent(parent[x]);// 递归查找
}

通过下面的图，我们发现，普通的查找过程相对较麻烦，例如寻找d结点的根节点，我们需要通过 $d->c->b->a$ 才能最终找到。

但是，如果我们使用路径压缩算法，那么只需要查找一次，就能确定d结点的结点，即 $d->a$ 。

图3 路径压缩（优化一）

//【递归版本】
// 改进查找算法：完成路径压缩，将x的上级直接变为根结点，那么树的高度就会大大降低
int find_parent(int x) // 查找结点x的根结点
{
    if(parent[x] == x) // 递归出口：x的上级为x本身，即x为根结点
    {        
        return x;      
    }
    return parent[x] = find_parent(parent[x]);// 递归查找，此代码相当于先找到根结点rootx，然后pre[x]=rootx
}

//【路径压缩的另一种写法】
//【个人更偏向于这种写法】 
int find_parent(int x)
{
    if(parent[x]!=x)parent[x]=find_parent(parent[x]);
    return parent[x];
}

【合并】

并查集的合并也非常简单，就是将一个集合的树根指向另一个集合的树根。

图4 并查集的合并

//【并】
// 朴素合并 
void unite(int x,int y)
{
    int root_x, root_y;
    root_x = find_parent(x);
    root_y = find_parent(y);
    if(root_x!=root_y)parent[root_y]=root_x;
}

也可以采用一种优化方法——按秩合并，注意初始化的时候需要将 $r数组$ 全部置0。

图5 按秩合并（优化二）

//【并】
// 按秩合并 
void unite(int x,int y)
{
    int root_x, root_y;
    root_x = find_parent(x);
    root_y = find_parent(y);
    // 属于同一个集合 
    if(root_x == root_y)return;
    // 属于不同集合 
    //令 y的根结点的上级为 root_x
    if(r[root_x] > r[root_y])parent[root_y] = root_x;         
    else
    {
        // 秩相等，合并之后秩需要加 1 
        if(r[root_x] == r[root_y])r[root_y]++;
        parent[root_x] = root_y;
    }
}

并查集的分析与用法：

时空复杂度：

时间复杂度：
同时使用路径压缩、按秩（rank）合并优化的程序每个操作的平均时间仅为 $O(\alpha(n))$ ，其中 $\alpha(n)$ 是 $n=f(x)=A(x,x)$ 的反函数， $A$ 是急速增加的阿克曼函数。因为 $\alpha(n)$ 是其反函数，故 $\alpha(n)$ 在 $n$ 十分巨大时还是小于 5。因此，平均运行时间是一个极小的常数。实际上，这是渐近最优算法：Fredman 和 Saks 在 1989 年解释了 $\Omega(\alpha(n))$ 的平均时间内可以获得任何并查集。
空间复杂度：
$O(n)$ （n为元素个数）
按秩合并会多一个保存秩的辅助空间，即 $数组r$ 。