并查集(Union-Find Set),也叫 Disjoint Set,由 Bernard A. Galler和Michael J. Fischer 在 1964 年提出,它主要是用来解决动态连通性问题。

什么是动态连通性问题?

如上图,若两点之间存在一条路线可以相互连接,那么这两个点就是连通的。现在如果我们一边新加入更多的点和路径,一边又要立即得到随机某两点是否连通,那么这该如何实现呢?

算法分析与实现

并查集的思想非常简单,把那些彼此连通的点连起来形成一棵树,如下图,

那么我们要判断某两点是否连通,只需判断它们的根是否相同即可。代码如下,

#include <iostream>

using namespace std;

#define N 10

int pre[N];

void Init()
{
    for (int i = 0; i < N; i++)
        pre[i] = i;
}

int Find(int i)
{
    if (pre[i] == i)
        return i;

    int i_parent = pre[i];
    int i_root = Find(i_parent);

    return i_root;
}

void Union(int i, int j)
{
    int i_root = Find(i);
    int j_root = Find(j);

    if (i_root == j_root)
        return;

    pre[i_root] = j_root;
}


int main()
{
    Init();

    Union(2, 9);
    Union(4, 9);
    Union(3, 4);
    Union(5, 6);

    // 判断 3 和 5 是否连通
    if (Find(3) == Find(5))
        cout << "3 和 5 连通.\n";
    else
        cout << "3 和 5 不连通.\n";

    return 0;
}

算法优化

从上面的代码可以看出,算法的复杂度主要在 Find 函数中,而 Find 的快慢主要由树的高度决定,那么我们的问题就转化为如何降低树的高度,常用的方法有两个:Path CompressionUnion By Rank

(1)Path Compression(路径压缩)

因为我们只想要快速地找到根结点,对沿途经过的那些结点并不关心,因此可以在 Find 查找过程中,将沿途经过的每一个结点的父亲直接设置为根结点,如下图,

int Find(int i)
{
    if (pre[i] == i)
        return i;

    int i_parent = pre[i];
    int i_root = Find(i_parent);

    pre[i] = i_root; // 路径压缩

    return i_root;
}

从上图可以看到,压缩后,树的高度变低了。

但我们要清楚,路径压缩其实是牺牲了路径完整性来求得更高效的运行速度,对于某些需要输出路径的应用场景,路径压缩这种优化就无法使用了。

(2)Union By Rank(按秩合并)

Rank 翻译为 "秩",在这里,我们可以简单地理解成 "树的高度",见下图,

void Union(int i, int j)
{
    int i_root = Find(i);
    int j_root = Find(j);

    if (i_root == j_root)
        return;

    if (rank[i_root] > rank[j_root])
        swap(i_root, j_root);

    pre[i_root] = j_root;

    if (rank[i_root] == rank[j_root]) // 两个秩相同的树合并,则整体的秩就会增加 1
        rank[j_root]++;
}

(3)更多的优化方法

上面讲的只是平时常用的两种,在维基上还有更多的优化方法,包括 Path Having、Path Splitting 等等,需要了解的朋友可以到这里

优化后的代码

下面的代码同时使用了路径压缩和按秩合并优化。

#include <iostream>
#include <algorithm>

using namespace std;

#define N 10

int pre[N];
int rank[N];

void Init()
{
    for (int i = 0; i < N; i++)
    {
        pre[i] = i;
        rank[i] = 0;
    }
}

int Find(int i)
{
    if (pre[i] == i)
        return i;

    int i_parent = pre[i];
    int i_root = Find(i_parent);

    pre[i] = i_root; // 路径压缩

    return i_root;
}

void Union(int i, int j)
{
    int i_root = Find(i);
    int j_root = Find(j);

    if (i_root == j_root)
        return;

    if (rank[i_root] > rank[j_root])
        swap(i_root, j_root);

    pre[i_root] = j_root;

    if (rank[i_root] == rank[j_root]) // 两个高度相同的树合并则整体的高度就会增加
        rank[j_root]++;
}

int main()
{
    Init();

    Union(2, 9);
    Union(4, 9);
    Union(3, 4);
    Union(5, 6);

    // 判断 3 和 5 是否连通
    if (Find(3) == Find(5))
        cout << "3 和 5 连通.\n";
    else
        cout << "3 和 5 不连通.\n";

    return 0;
}

算法复杂度

当不采用任何优化的情况下,并查集每次操作的最差时间复杂度为 $O(n)$,即树退化为链表的时候。

当仅采用路径压缩优化时,每次操作的最差时间复杂度为 $O(1+log_{2+f/n}n)$,这个值比 $O(log_2n)$ 小,其中 $f$ 为查找次数。

当仅使用按秩合并优化时,每次操作的最差时间复杂度为 $Θ(log_2n) $。

当同时使用路径压缩和按秩合并优化时,摊还分析后,每次操作的最差时间复杂度为 $O(log^∗n)$,其中 $log^∗n$ 是 Iterated Logarithm 函数,实际使用中,它的值不超过 5,如下图,这也就是说每次操作的实际复杂度,只有 $O(1)$。

应用场景

并查集,小巧、易写、高效。它的应用非常广泛,可以说是数据结构中必掌握算法之一。

  1. 网络连通性检测;
  2. 图像处理;
  3. Kruskal 最小生成树算法;
  4. ......

参考

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2019-12-09
原文链接:https://ethsonliu.com/2019/12/union-find-set.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。