大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

深夜学算法之Union Find Set:动态连通

1. 前言

并查集(Union Find Set),也称为不相交集数据结构(Disjointed Set Data Structure),两个名字各自概括了这一数据结构的部分特征。简单地讲,并查集维护了一列互不相交的集合S1、S2、S3、…,支持查找(find)与合并(union)两种操作。

  • find
    找到元素所在的集合,通常返回该集合的代表元(representative)
    元素a与元素b是否属于同一个集合,只要判断find(a)与find(b)是否相等
  • union
    将两个集合合并为一个集合
    将元素a与元素b所在的集合合并为一个集合,使用union(a,b)

我的实现在这里

2. 原理

2.1 基础算法

UnionFindSet用树表示集合,所谓维护一列互不相交的集合也就是有许多棵树。每棵树的元素属于一个集合,树根的元素就是集合的代表元,所以UnionFindSet实际上维护了一个多棵树构成的森林。

  • find(x)就是找x所在的树的树根
  • union(x, y)就是合并x和y所在的树

来看UnionFindSet的定义:

class UnionFindSet {
    public:
        UnionFindSet(int n);
        int Find(int x);
        void Union(int x, int y);
    private:
        std::vector<int> parent;
};

与常见的树形数据结构不同,并查集的链接关系不是从parent指向child而是从child指向parent,这个链接信息保存在parent数组里。

  1. 若parent[x] == x,则x就是x所在树的树根
  2. 若parent[x] != x,则x是parent[x]的子节点

解释完parent的含义,Find的实现方法也就呼之欲出了。

int UnionFindSet::Find(int x) {
    if (parent[x] == x)
        return x;
    else
        return Find(parent[x]);
}

构造函数UnionFindSet(int n)表示最初有n个互不相交的集合,代表元分别为0、1、2、…(n-1)。

UnionFindSet::UnionFindSet(int n) {
    parent.resize(n);
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }
}

要合并两棵树,只要把一棵根节点的parent设为另一棵树的根节点。

void UnionFindSet::Union(int x, int y) {
    int root_x = Find(x);
    int root_y = Find(y);
    if (root_x == root_y)
        return;
    parent[root_y] = root_x;
}

用图形解释find和union中parent的作用,其中child在下层,parent在上层。
3的parent是2,那么调用find(3)时:

  • parent[3] = 2,调用find(2)
  • parent[2] = 2,返回2

调用find(3)

调用union(1, 3)时:

  • 调用find(1),得到root_x = 0
  • 调用find(3),得到root_y = 2
  • parent[2] = 0

调用union(1, 3)

2.2 优化合并

并查集就是一组树构成的森林,与通常的搜索树相比只是链接关系从parent->child变成了child->parent,所以也会出现搜索树中的问题。极端情况下n个节点像链表那样构成n层,对于最底层的节点,find复杂度自然是O(n),而union由于调用find复杂度也会变成O(n)。
既然树的高度影响效率,那么可以设法避免高树出现,也就是本小节的优化合并;也可以设法把高树变矮,也就是下一小节的路径压缩。

优化合并就是优化union操作,简单粗暴地讲,就是合并时永远把矮树作为高树的子树。判断哪棵树比较矮有union-by-size和union-by-height两种做法,union-by-height是在类中添加height数组记录每个节点的高度,union-by-size是在类中添加size数组记录每个节点的子节点数量,两者效果完全相同。我采用union-by-height,感兴趣union-by-size的可以看这里

在类中添加height数组:

class UnionFindSet {
    public:
        UnionFindSet(int n);
        int Find(int x);
        void Union(int x, int y);
        void Display(void);
    private:
        std::vector<int> parent;
        std::vector<int> height;
};

修改构造函数UnionFindSet(int n):

UnionFindSet::UnionFindSet(int n) {
    parent.resize(n);
    height.resize(n);

    for (int i = 0; i < n; ++i) {
        parent[i] = i;
        height[i] = 0;
    }
}

新的union算法:

void UnionFindSet::Union(int x, int y) {
    int root_x = Find(x);
    int root_y = Find(y);

    if (root_x == root_y)
        return;

    if (height[root_x] > height[root_y]) {
        parent[root_y] = root_x;
    } else if (height[root_x] < height[root_y]) {
        parent[root_x] = root_y;
    } else {
        parent[root_y] = root_x;
        ++height[root_x];
    }
}

注意只有根节点高度相同时需要更新height,因为两棵树高度不相等时矮的那棵至少比高的矮一层。因此对于有n个节点的并查集,height的最大值为lgn,所以find和union的算法复杂度都至多为O(lgn)。

2.3 路径压缩

路径压缩就是改造find操作,直接来看代码:

int UnionFindSet::Find(int x) {
    if (parent[x] == x)
        return x;
    else {
        int result = Find(parent[x]);
        parent[x] = result;
        return result;
    }
}

也就是说在查找时,把查找路径上节点的parent都设为根节点,从而把这棵树「压平」,加速以后的查找。用图形演示find(4)就是:


调用find(4)前

调用find(4)后

这时find操作也会改变树高,所以height数组里的值就不是准确的树高,而是估计树高(estimated height),或者称为秩(rank),这时做法也成为union-by-rank。

3. 应用

并查集可以用于检测无向图中是否存在环。假设无向图中有v个节点和e条边,用伪代码形式写就是:

bool detect_cycle(v, e) {
    u = UnionFindSet(v)
    for (int i = 0; i < e.size; ++i) {      

        (p, q) = e(i); // 取得第i条边的两个节点

        if (u.find(p) == u.find(q))
            return true;
        u.union(p, q);
    }
    return false;
}

所以可以把并查集用在kruskal最小生成树算法里,实现可以参考这里

注意与BFS/DFS相比,并查集检测速度快,但只能检测环的存在,不能确定哪些节点构成了环。

4. 参考资料

5. 附录:关于代表元

下图是一张典型的无向图,有a、b、c、d、e五个节点:


一张典型的无向图

S(x) 表示包含节点x的极大连通子图里节点的集合,显然有:

S(a) = S(b)= S(c) = { a,b,c }
S(d) = S(e) = { d,e }

不同的集合有 {a,b,c} 和 {d,e} 两个,而且它们互不相交。代表元是一个集合里的典型元素,可以从集合里任意选取,比如 {a,b,c} 的代表元可以用a,也可以用b或c。由于集合互不相交,所以代表元互不相同,判断「两个元素是否属于同一个集合」等价于判断「两个元素所在集合的代表元是否相等」。

find(x) 就是找到元素x所在集合的代表元。
分别取a、d为两个集合的代表元,那么有:

find(a) = find(b) = find(c) = a
find(d) = find(e) = d

b和e不在同一个集合里,相应的有find(b)不等于find(e)。

现在我们在原图里添加一条连接b和d的边:


添加边后

发生了什么事情?图上两个互相不连通的部分结合了,这时应该有:

S(a) = S(b)= S(c) = S(d) = S(e) = { a,b,c,d,e }

union(x, y) 就是将元素x和元素y所在的集合合并成一个集合。
union(b, d)之后,b所在的、以a为代表元的集合,与d所在的、以d为代表元的集合合成了一个大的新集合,将这个新集合代表元取为a,则有:

find(a) = find(b) = find(c) = find(d) = find(e) = a

b和e现在在同一个集合里,所以有find(b)等于find(e)。