MENU

并查集

August 19, 2018 • 文章

一:背景

并查集(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. ......

七:参考文献

Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 2 条评论
  1. anonymous anonymous

    您好,看了您的博客感觉写的特别好,受益匪浅,但是这篇有个疑问,rank没有计数,是不是每次find,在return i_root之前都要计数?还有swap那也没有看懂,6和9是怎么交换的,谢谢了。

    1. @anonymous
      1. rank的计数是放在Union里的;
      2. 之所以用swap,是为了减少代码量。union-by-rank就是拿小rank的树接到大的rank的树,所以需要先判断两棵树rank的大小,你也可以用if else来做,但这样代码会变多,而且会有多余的判断,所以用了swap。