高级数据结构：并查集（Java 实现）

2019-01-25 本文已影响15人李威威

image

并查集的内容非常简单，代码的每个方法的实现都很短，难在灵活应用。

并查集基础

为什么叫并查集？因为在这个数据结构中，我们要针对“并”和“查”这两种操作展开研究。并是并什么？并是把两个元素合并在一起。查是查什么？查两个元素是不是连接在一起；

并查集主要研究的问题。并查集主要用来解决连通问题，即抽象概念中结点和结点是否连接。而路径问题，不仅仅要考虑连通问题，我们还要往往还需要求出最短路径；
并查集问题能做的事情比路径问题更少，它更专注于（1）判断连接状态（查），（2）改变连接状态（并）；
具体说来，并查集的代码需要实现以下的 3 个功能：

find(int p)：查找元素 p 所对应的集合。
union(int p, int q)：合并元素 p 和元素 q 所在的集合。
connected(int p, int q)：查询元素 p 和元素 q 是不是在同一个集合中。

因此，我们的并查集其实就是要实现下面的这个接口：

public interface IUnionFind {

    // 并查集的版本名称，由开发者指定
    String versionName();

    // p (0 到 N-1)所在的分量的标识符
    int find(int p);

    // 如果 p 和 q 存在于同一分量中则返回 true
    boolean connected(int p, int q);

    // 在 p 与 q 之间添加一条连接
    void union(int p, int q);

}

并查集算法第 1 版：quick-find

从 quick-find 这个名字上看，我们这一版的实现，对于 find(int p) 这个操作来说是高效的。

通过这一节的学习，我们可以知道：

并查集的第 1 种实现（使用 id 数组管理查和并操作），能够快速地实现 find(int p) 这个操作；
quick-find 对于 union(int p, int q) 这个操作是低效的，因为需要遍历整个并查集。

并查集的基本数据表示：使用数组就可以表示了，这个数组我们可以起一个名字叫做 id；
初始化的情况下，每一个元素的 id 都是不一样的。如果是一样的，表示是属于同一个集合内的元素；

基于 id 的 quick-find 的思路：设置 id 数组，表示每个元素的分量标识。

基于 id 的 quick-find

find(int p) 这个操作的时间复杂度是 $O(1)$ ，而 union(int p, int q) 这个操作的时间复杂度是 $O(n)$ ，要全部遍历并查集中的元素，把其中一个分量标识的所有结点的编号更改为另一个一个分量标识。

例如上面的表格中，如果我们要将第 1 行的 0 和 1 执行 union(int p, int q) 操作，有两种方式：第 1 种方式：把第 1 行的 0，2，4，6，8 的 id 全改成 1；第 2 种方式：把第 1 行的 1，3，5，7，9 的 id 全改成 0。我们可以看到，union(int p, int q) 的操作完全是和问题的规模成正比的，所以 quick-find 下的 union(int p, int q) 操作时间复杂度是 $O(n)$ 。

public class UnionFind1 implements IUnionFind {

    private int[] id; // 分量 id

    private int count; // 联通分量的数量

    public UnionFind1(int n) {
        this.count = n;
        // 初始化分量 id 数组
        id = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
    }

    @Override
    public String versionName() {
        return "并查集的第 1 个版本，基于 id 数组，quick-find";
    }

    // 以常数时间复杂度，返回分量的标识符，与并查集的规模是无关的，这一步很快
    // 因此我们称这个版本的并查集是 quick-find
    @Override
    public int find(int p) {
        return id[p];
    }

    @Override
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    // 因为需要遍历数组中的全部元素，所以其实这个版本效率并不高
    @Override
    public void union(int p, int q) {
        int pid = find(p);
        int qid = find(q);

        // 如果 p 和 q 已经在相同的分量之中，则什么都不做
        if (pid == qid) {
            return;
        }

        // 将 p 的分量重新命名为 q 的名称
        for (int i = 0; i < id.length; i++) {
            if (find(i) == pid) {
                id[i] = qid;
            }
        }
        // 每次 union 以后，连通分量减 1
        count--;
    }
}

优化思路：因为 union(int p, int q) 慢，所以我们就想办法让 union(int p, int q) 快起来。

并查集算法第 2 版：quick-union

使用 id 数组在进行 union(int p, int q) 的时候，要遍历整个数组中的结点，这种方式效率不高，因此，我们换一种思路。

我们不再使用 id 数组，而使用 parent 数组，parent 数组的定义是：parent[i] 表示索引为 i 这个结点的父亲结点的索引，在这样的定义下，根结点的父亲结点是自己。

从孩子结点指向父亲结点

此时查询结点 p 和结点 q 相连这件事情，就是我们分别追溯 parent[p] 和 parent[q] （可以看到这样的过程很像在一棵树中的操作），查询到 parent[p] 和 parent[q] 的根结点，如果根结点相同，那么它们就同属于一个集合。
这样看来，find(int p) 好像费点劲，这也是我们接来下的几个并查集优化的方向，都是在 find(int p) 上做文章，但这保证了 union(int p, int q) 很快，我们只需把其中一个结点的父结点指向另一个结点的根结点（而谁的父结点指向谁的根结点，也是我们后几版并查集优化的方向），就完成了 union(int p, int q) 的操作。此时 union(int p, int q) 的操作只须要一行代码：

parent[pRoot] = qRoot;

初始化的时候，我们将每个元素都指向自己，此时表示这 $10$ 个结点互相之间没有连接关系。如下表所示：

初始化的时候，我们将每个元素都指向自己

画出的示意图如下。

初始化的时候，我们将每个元素都指向自己

从正确性上来说，谁的根指向谁的根都是可以的。但是在实际运行的时候，我们会发现，我们应该将层级较少的根指向层级较多的根，这样做是为了保证我们的并查集形成的树的高度不会增加，这样在 find 的时候，追溯的层数不会增加。我们在查找根的时候，应该使得查找的层数最少。

public class UnionFind2 implements IUnionFind {

    private int[] parent; // 第 i 个元素存放它的父元素的索引

    private int count; // 联通分量的数量

    public UnionFind2(int n) {
        this.count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    @Override
    public String versionName() {
        return "并查集的第 2 个版本，基于 parent 数组，quick-union";
    }

    @Override
    public int find(int p) {
        // 跟随链接找到根结点
        while (parent[p] != p) { // 只要不是根结点
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void union(int p, int q) {
        int pRoot = find(p); // 将 p 归并与之相同的分量中
        int qRoot = find(q); // 将 q 归并与之相同的分量中

        // 如果 p 和 q 已经在相同的分量之中，则什么都不做
        if (pRoot == qRoot) {
            return;
        }
        // 如果 parent[qRoot] = pRoot; 也是可以的，即将其中一个结点指向另一个结点
        parent[pRoot] = qRoot;
        // 每次 union 以后，连通分量减 1
        count--;
    }
}

并查集算法第 3 版：quick-union 基于 size 的优化

我们发现 union 4,9 与 union 9,4 其实是一样的，也就是把谁的根指向谁的根，这一点从正确性上来说是无关紧要的，但是对于 find 的时间复杂度就会有影响。为此，我们做如下优化。
在合并之前做判断，具体做法是，计算每一个结点有多少个元素直接或者间接地以它为根，我们应该将集合元素少的那结点的根指向集合元素多的那个结点的根。这样，形成的树就会更高概率地形成一棵层数较低的树。
为此，我们再引入一个 size 数组，size[i] 的定义是：以第 i 个结点为根的集合的元素的个数。
在初始化的时候 size[i] = 1，find 和 isConnected 操作中我们都不须要去维护 size[] 这个数组，唯独在 unionElements 的时候，我们要维护 size 数组的定义。

// union-find 算法的实现（加权 quick-union 算法）
public class UnionFind3 implements IUnionFind {

    private int[] parent; // 第 i 个元素存放它的父元素的索引

    private int count; // 联通分量的数量

    private int[] size; // 以当前索引为根的树所包含的元素的总数

    public UnionFind3(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            // 初始化时，所有的元素只包含它自己，只有一个元素，所以 size[i] = 1
            size[i] = 1;
        }
    }

    @Override
    public String versionName() {
        return "并查集的第 3 个版本，基于 parent 数组，quick-union，基于 size";
    }

    // 返回索引为 p 的元素的根结点的索引
    @Override
    public int find(int p) {
        // 跟随链接找到根结点
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean connected(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        return pRoot == qRoot;
    }

    @Override
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        // 这一步是与第 2 版不同的地方，我们不是没有根据地把一个结点的根结点的父结点指向另一个结点的根结点
        // 而是将小树的根结点连接到大树的根结点
        if (size[pRoot] > size[qRoot]) {
            parent[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        } else {
            parent[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        }
        // 每次 union 以后，连通分量减 1
        count--;
    }
}

并查集算法第 4 版：quick-union 基于 rank 的优化

使用 size 来决定将哪个结点的根指向另一个结点的根，其实并不太合理，但并不能说不正确，因为谁的根指向谁的根，其实都没有错，下面就是一个特殊的情况。

因为我们总是期望这棵树的高度比较低，这样，我们在 find 的时候，就能通过很少的步数来找到根结点，进而提高 find 的效率。

此时，我们引入 rank 数组，其定义是： rank[i] 表示以第 i 个元素为根的树的高度。

public class UnionFind4 implements IUnionFind {

    private int[] parent;

    private int count;

    // 以索引为 i 的元素为根结点的树的深度（最深的那个深度）
    private int[] rank;

    public UnionFind4(int n) {
        this.count = n;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            // 初始化时，所有的元素只包含它自己，只有一个元素，所以 rank[i] = 1
            rank[i] = 1;
        }
    }

    @Override
    public String versionName() {
        return "并查集的第 4 个版本，基于 parent 数组，quick-union，基于 rank";
    }

    // 返回索引为 p 的元素的根结点
    @Override
    public int find(int p) {
        // 跟随链接找到根结点
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean connected(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        return pRoot == qRoot;
    }


    @Override
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        // 这一步是与第 3 版不同的地方
        if (rank[pRoot] > rank[qRoot]) {
            parent[qRoot] = pRoot;
        } else if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        } else {
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
        // 每次 union 以后，连通分量减 1
        count--;
    }
}

并查集算法第 5 版：quick-union 基于路径压缩的非递归实现

什么是路径压缩 path Compression？以上我们都是针对于 union 操作的优化，其实我们在 find 的时候，就可以对一棵树进行整理，让它的高度变低，这一点是基于并查集的一个特性：只要它们是连在一起的，其实谁指向谁，并不重要，所以，我们在接下来的讨论中看到的并查集的表示图，它们是等价的，即它们表示的都是同一个并查集。
路径压缩 path Compression 的思路：在 find 的时候一次又一次的整理，将并查集构造（整理）成一个与之等价的并查集，使得后续的每一次 find 这样的操作路径最短。
假设一个最极端的并查集的图表示如下：

极端的并查集的例子

我们开始找 4 的父亲结点，4 的父亲结点不是 4 ，说明不是根结点，此时，我们尝试 2 步一跳，将 4 的父亲结点“改成”父亲结点的父亲结点，于是得到一个等价的并查集：

与上一个并查集等价的并查集

下面我们该考察元素 2 了，2 的父亲结点是1，2 不是根结点，所以我们继续两步一跳，把 2 的父亲结点设置成它的父亲结点的父亲结点，于是又得到一个等价的并查集：

与上一个并查集等价的并查集

此时，整棵树的高度就在一次 find 的过程中被压缩了。

这里有一个疑问：即使我们在最后只差一步的情况下，我们跳两步，也不会出现无效的索引。其实，一步一跳，两步一跳，甚至三步一跳都没有关系。

画图画了这么多，代码实现起来只有一句：parent[p] = parent[parent[p]];编写的时候要注意这行代码添加的位置，画一个示意图，想想这个路径压缩的过程，不难写出。

public int find(int p) {
    // 在 find 的时候执行路径压缩
    while (p != parent[p]) {
        // 编写这句代码的时候可能会觉得有点绕，
        // 技巧是画一个示意图，就能很直观地写出正确的逻辑
        // 两步一跳完成路径压缩
        parent[p] = parent[parent[p]];
        p = parent[p];
    }
    return p;
}

根据上面的图，我们通过 find 操作执行路径压缩，最终形成的并查集如下：

与上一个并查集等价的并查集

并查集算法第 6 版：quick-union 基于路径压缩的递归实现

代码的实现的理解有一些绕，需要花一些时间才能想清楚）
压缩更彻底的路径压缩：其实我们不看上面的分析，我们想象路径压缩的目的是什么，就是让我们的并查集表示的树结构层数更低，那么最优的情况应该是下面这样，把一棵树压缩成2 层，所有的结点都指向一个根，这才是把一个并查集压缩到最彻底的情况。

从极端不好的并查集到极端好的并查集

那么，代码又应该如何实现呢？我们须要使用递归的思想。这一版代码的实现难点就在于：应该定义 find(p) 返回的是 p 这个结点的父结点。

/**
 * 返回索引为 p 的元素的根结点
 * 理解这个方法的关键点：我们就是要把这个结点的父结点指向根结点，
 * 既然父亲结点不是根结点，我们就继续拿父亲结点找根结点
 * 一致递归找下去，
 * 最后返回的时候，写 parent[p] 是可以的
 * 写 parent[parent[p]] 也是没有问题的
 *
 * @param p
 * @return
 */
public int find(int p) {
    // 在 find 的时候执行路径压缩
    assert p >= 0 && p < count;
    // 注意：这里是 if 不是 while，否则就变成循环
    if (p != parent[p]) {
        // 这一行代码的逻辑要想想清楚
        // 只要不是根结点
        // 就把父亲结点指向父亲结点的父亲结点
        parent[p] = find(parent[p]);
    }
    return parent[p];
}

最后，我们来比较一下基于路径压缩的两种方法。

路径压缩算法

并查集能够很好地帮助我们解决网络中两个结点是否连接的问题。但是，对于网络中的两个结点的路径，最短路径的问题，我们就要使用图来解决。

关于路径压缩的思考

写到这里，我们发现在路径压缩的过程中，我们之前引入的辅助合并的数组，不管是 rank 还是 size，它们的定义都不准确了，因为我们在路径压缩的过程中没有对它们的定义进行维护。这一点其实并不影响我们的算法的正确性，我们不去维护 rank 数组和 size 数组的定义，是因为第 1 点，难于实现，第 2 点 rank 数组还是 size 数组的当前实现仍然可以作为一个参考值，比起随机的做法要更有意义一些。

并查集算法第 7 版：易于理解的路径压缩算法

Python 实现：

class UnionFind7:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.count = n

    def find(self, p):
        """
        查找元素 p 根节点的编号
        :param p:
        :return:
        """
        assert 0 <= p < self.count
        root = p
        while root != self.parent[root]:
            root = self.parent[root]
        # 此时 root 就是大 boss
        # 下面这一步就是最直接的路径压缩：
        # 把沿途查找过的结点都指向 root
        while p != self.parent[p]:
            temp = self.parent[p]
            self.parent[p] = root
            p = temp
        return root

    def is_connected(self, p, q):
        """
        查询元素 p 和 q 是否属于同一个集合
        有共同的父亲，就表示它们属于同一个集合
        :param p:
        :param q:
        :return:
        """
        return self.find(p) == self.find(q)

    def union(self, p, q):
        """
        合并元素 p 和元素 q 所属于的集合
        O(n)复杂度
        :param p:
        :param q:
        :return:
        """

        p_id = self.find(p)
        q_id = self.find(q)
        if p_id == q_id:
            return
        # 任意指向即可
        self.parent[p_id] = q_id

LeetCode 上关于“并查集”的练习

LeetCode 第 200 题：岛屿的个数。

传送门：200. Number of Islands、200. 岛屿的个数。

LeetCode 第 547 题：朋友圈（这个题目的名字很接地气）

传送门：547. Friend Circles、547. 朋友圈。

我的 Python 解答：

class Solution(object):

    def findCircleNum(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        class UnionFind:
            def __init__(self, n):
                self.parent = [i for i in range(n)]

            def find(self, p):
                root = p
                while root != self.parent[root]:
                    root = self.parent[root]
                while p != self.parent[p]:
                    temp = self.parent[p]
                    self.parent[p] = root
                    p = temp
                return root

            def is_connected(self, p, q):
                return self.find(p) == self.find(q)

            def union(self, p, q):
                p_id = self.find(p)
                q_id = self.find(q)
                if p_id == q_id:
                    return
                self.parent[p_id] = q_id

        m = len(M)
        union_find_set = UnionFind(m)
        for i in range(m):
            for j in range(i):
                if M[i][j] == 1:
                    union_find_set.union(j, i)
        counter = 0
        # print(union_find_set.parent)
        for index, parent in enumerate(union_find_set.parent):
            if index == parent:
                counter += 1
        return counter