并查集(Disjoint-Set)

2020-06-12 约 2817 字预计阅读 6 分钟次阅读

基本介绍

并查集(Disjoint-Set) 又被称为union-find算法。它是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以进行合并操作，但是却无法进行分割操作

合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

当然，这样的定义未免太过学术化，看完后恐怕不太能理解它具体有什么用。所以我们先来看看并查集最直接的一个应用场景：亲戚问题。

题目背景若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。题目描述规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。输入格式第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。输出格式 P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

这其实是一个很有现实意义的问题。我们可以建立模型，把所有人划分到若干个不相交的集合中，每个集合里的人彼此是亲戚。为了判断两个人是否为亲戚，只需看它们是否属于同一个集合即可。因此，这里就可以考虑用并查集进行维护了。

并查集的引入

并查集的重要思想在于，用集合中的一个元素代表集合。我曾看过一个有趣的比喻，把集合比喻成帮派，而代表元素则是帮主。接下来我们利用这个比喻，看看并查集是如何运作的。最开始，所有大侠各自为战。他们各自的帮主自然就是自己。（对于只有一个元素的集合，代表元素自然是唯一的那个元素）现在1号和3号比武，假设1号赢了（这里具体谁赢暂时不重要），那么3号就认1号作帮主（合并1号和3号所在的集合，1号为代表元素）。现在2号想和3号比武（合并3号和2号所在的集合），但3号表示，别跟我打，让我帮主来收拾你（合并代表元素）。不妨设这次又是1号赢了，那么2号也认1号做帮主。现在我们假设4、5、6号也进行了一番帮派合并，江湖局势变成下面这样：现在假设2号想与6号比，跟刚刚说的一样，喊帮主1号和4号出来打一架（帮主真辛苦啊）。1号胜利后，4号认1号为帮主，当然他的手下也都是跟着投降了。好了，比喻结束了。如果你有一点图论基础，相信你已经觉察到，这是一个树状的结构，要寻找集合的代表元素，只需要一层一层往上访问父节点（图中箭头所指的圆），直达树的根节点（图中橙色的圆）即可。根节点的父节点是它自己。我们可以直接把它画成一棵树：

代码

属性

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


int[] father; // 父节点
    int[] rank; // 以cur为根节点的树的深度，只有自己时深度为1

    public DisjointSet(int n) {
        this.father = new int[n];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
            rank[i] = 1;
        }
    }

查询

我们只关心一个元素对应的根节点，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步，像这样：其实这说来也很好实现。只要我们在查询的过程中，把沿途的每个节点的父节点都设为根节点即可。下一次再查询时，我们就可以省很多事。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


    /**
     * 查找根节点
     *
     * @param x
     * @return
     */
    public int find(int x) {
        int son = x;
        while (x != father[x]) {
            x = father[x]; // 老祖宗
        }
        // 路径压缩,此时x是老祖宗
        int temp;
        while (son != x) {
            temp = father[son]; // 保存son的父亲， 待会将他也指向老祖宗
            father[son] = x; // 将son指向老祖宗， 下次查询遍历一次就知道了
            son = temp;
        }
        return x;
    }

按秩合并

有些人可能有一个误解，以为路径压缩优化后，并查集始终都是一个菊花图（只有两层的树的俗称）。但其实，由于路径压缩只在查询时进行，也只压缩一条路径，所以并查集最终的结构仍然可能是比较复杂的。例如，现在我们有一棵较复杂的树需要与一个单元素的集合合并：假如这时我们要merge(7,8)，如果我们可以选择的话，是把7的父节点设为8好，还是把8的父节点设为7好呢？

当然是后者。因为如果把7的父节点设为8，会使树的深度（树中最长链的长度）加深，原来的树中每个元素到根节点的距离都变长了，之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩，但路径压缩也是会消耗时间的。而把8的父节点设为7，则不会有这个问题，因为它没有影响到不相关的节点。

这启发我们：我们应该把简单的树往复杂的树上合并，而不是相反。因为这样合并后，到根节点距离变长的节点个数比较少。

我们用一个数组rank[]记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的子树的深度）。一开始，把所有元素的rank（秩）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。路径压缩和按秩合并如果一起使用，时间复杂度接近$O(n)$，但是很可能会破坏rank的准确性。

值得注意的是，按秩合并会带来额外的空间复杂度，可能被一些卡空间的毒瘤题卡掉。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


    /**
     * 按秩合并
     * 并查集判断图的环路方法是按边来遍历合并集合，当遍历合并一条边出现两个顶点早就处于同一个集合即可判定出现环路
     *
     * @param x
     * @param y
     * @return 0 指向同一个根节点出现环路 1合并成功
     */
    public int merge(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) { //同一个根节点， 返回0， 在构造最小生成树时会用到，表示出现环
            return 0;
        }
        if (rank[fx] > rank[fy]) {
            father[fy] = fx;
        } else if (rank[fx] < rank[fy]) {
            father[fx] = fy;
        } else {
            father[fy] = fx;
            rank[fx]++;
        }
        return 1;
    }

为什么深度相同，新的根节点深度要+1？如下图，我们有两个深度均为2的树，现在要merge(2,5)：这里把2的父节点设为5，或者把5的父节点设为2，其实没有太大区别。我们选择前者，于是变成这样：显然树的深度增加了1。另一种合并方式同样会让树的深度+1。

并查集的应用

并查集的应用还有很多，例如最小生成树的Kruskal算法等。凡是涉及到元素的分组管理问题，都可以考虑使用并查集进行维护。

完整代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


package com.eh.ftd.dsa.ds;

/**
 * 并查集
 *
 * @author David Li
 * @create 2020/07/05 02:15
 */
public class DisjointSet {
    int[] father; // 父节点
    int[] rank; // 以cur为根节点的树的深度，只有自己时深度为1

    public DisjointSet(int n) {
        this.father = new int[n];
        this.rank = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 查找根节点
     *
     * @param x
     * @return
     */
    public int find(int x) {
        int son = x;
        while (x != father[x]) {
            x = father[x]; // 老祖宗
        }
        // 路径压缩,此时x是老祖宗
        int temp;
        while (son != x) {
            temp = father[son]; // 保存son的父亲， 待会将他也指向老祖宗
            father[son] = x; // 将son指向老祖宗， 下次查询遍历一次就知道了
            son = temp;
        }
        return x;
    }

    /**
     * 按秩合并
     *
     * @param x
     * @param y
     * @return 0 指向同一个根节点 1合并成功
     */
    public int merge(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) { //同一个根节点， 返回0， 在构造最小生成树时会用到，表示出现环
            return -1;
        }
        if (rank[fx] > rank[fy]) {
            father[fy] = fx;
        } else if (rank[fx] < rank[fy]) {
            father[fx] = fy;
        } else {
            father[fy] = fx;
            rank[fx]++;
        }
        return 1;
    }
}

目录