什么是并查集

并查集主要可以用来解决网络中节点的连接问题。注意，这里的网络是一个抽象概念，比如社交网络等。

连接问题和路径问题是有区别的，连接问题比路径问题要回答的问题少。比如有两个两节 a 和 b，如果是连接问题的话我们只需要判断他们两个是否连接。但如果是路径问题，我们就需要找出所有的连接可能性。

并查集主要支持下面两种操作：

  • union(p, q) 将个元素合并到一个集合
  • isConnected(p, q) 用于判断两个节点是否连接

也就是需要实现下面两个最主要的方法：

  1. public interface UF {
  2.     int getSize();
  3.     // 判断 p 和 q 是否连通
  4.     boolean isConnected(int p, int q);
  5.     // 将 p 和 q 连接
  6.     void unionElements(int p, int q);
  7. }

Quick Find

我们可以给每个数据做一个编号，对于每一个元素并查集存储的是这个元素所属的集合的 id 。我们可以用数组表示：
Snip20220123_76.png
下面我们来实现

代码实现

public class UnionFind1 implements UF {
    // id 数组中存储的是每一项所属的集合 id
    private int[] id;
    public UnionFind1(int size){
        id = new int[size];
        // 刚开始的时候每个元素都是单独的一个集合
        for (int i = 0; i < size; i++)
            id[i] = i;
    }

    @Override
    public int getSize() {
        return id.length;
    }
    //  查找元素 p 所对应的集合编号
    private int find(int p) {
        if (p < 0 || p >= id.length)
            throw new IllegalArgumentException("p is not bound.");
        // 找个某个元素所属的集合
        return id[p];
    }

    // 查看元素 p 和元素 q 是否所属一个集合
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 合并元素 p 和元素 q 所属的集合
    @Override
    public void unionElements(int p, int q) {
        // 查找 p 号元素所属的集合 id
        int pId = find(p);
        // 查找 q 号元素所属的集合 id
        int qId = find(q);

        // 如果 p 和 q 所属的集合 id 是同一个，说明是同一个集合，这时就不用合并了
        if (pId == qId) return;

        for (int i = 0, len = id.length; i < len; i++)
            // 如果当前元素的集合 id 和 pId，就将当前元素的集合 id 改为 qId，也就是将当前元素合并到 q 所属集合中
            if (id[i] == pId)
                id[i] = qId;
    }
}

从上面的实现代码中我们可以看出 find 操作是很快的，时间复杂度为 O(1)，相应的 isConnected 操作的时间复杂度也是 O(1)。由于上面实现方式 find 操作很快，所以这种方式叫做 Quick Find。但是 unionElements 操作的时间复杂度却为 O(n) ，我们下面来看看怎么优化这个操作。

Quick Union

我们将每一个元素看作是一个节点，刚开始的时候每个节点指向它自己。当有多个节点的时候，每个节点都可以看成是一颗树，整个图就可以看成是一片森林。
Snip20220125_87.png
如果我们将 0，1 进行合并后得到下面这样的图
Snip20220125_88.png
将 2，0 进行合并：
Snip20220125_89.png
你可能会问，为什么不将 2 放到 0 后面呢，这是因为如果把 2 放到 0 后面，就形成了一个链表，查找操作的时间复杂度就成了 O(n)。从这里我们就可以得出：将两个树进行合并的时候，是这个树的根节点挂载到要合并树的根节点上。

从上面的操作我们可以看出合并操作的时间复杂度为O(H)，H 代表树的高度，比上面讲的 Quick Find 的复杂度要小。因为树的高度肯定要小于数据的总长度 n。但是查找操作由原来的 O(1) 变成了 O(H)。
Snip20220131_131.png

代码实现

public class UnionFind2 implements UF {
    // parent 数组存储的是每个节点指向的节点
    private int[] parent;
    public UnionFind2(int size) {
        parent = new int[size];
        // 刚开始的时候每个节点都指向它自己
        for (int i = 0; i < size; i++)
            // parent[i] 表示的是第 i 个元素指向哪个节点
            parent[i] = i;
    }

    // 查找元素 p 所对应的集合编号
    private int find(int p) {
        if (p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is not bound.");

        // p 和 parent[p] 不相等就一直向上找，直到找到了它自己，也就是根节点，这个时候返回即可
        while(p != parent[p])
            p = parent[p];
        return p;
    }
    @Override
    public int getSize() {
        return parent.length;
    }

    // 查看元素 p 和 q 是否属于同一个集合
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 合并元素 p 和元素 q 所属的集合
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        parent[pRoot] = qRoot;
    }
}

基于size的优化

第一版的并查集使用数组模拟每个数据所属的集合是什么；第二版的并查集，虽然我们依然使用数组进行数据关系的存储，但我们让数据形成了一片森林，我们让森林中的每棵树节点之间的关系都是孩子指向父亲 。这样我们可以通过任意节点查询到这颗树的根节点是谁。相应的我们也就知道了对于每个节点来说它所属的集合编号是谁。

上面我们实现了两个版本的并查集，下面我们来测试下它们的性能：

import java.util.Random;

public class Main {
    private static double testUF(UF uf, int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a, b);
        }

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a, b);
        }

        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int m = 100000;
        int size = 100000;
        UnionFind1 uf1 = new UnionFind1(size);
        System.out.println("UnionFind1：" + testUF(uf1, m) + "s");
        UnionFind2 uf2 = new UnionFind2(size);
        System.out.println("UnionFind2：" + testUF(uf2, m) + "s");
    }
}

运行上述代码，打印结果如下：

UnionFind1：0.025828826s
UnionFind2：10.209943863s

我们可以看到结果很是让人惊讶呀，第二个版本的并查集更耗费性能了？这是为啥呢？最主要的原因是第二版的并查集的查找和合并操作的时间复杂度都是 O(H)，在合并的时候最差的情况是退化成了一个链表。下面我们来对合并操作进行优化，优化的思路就是在合并的时候判断下两个树哪个节点少，就将节点少的合并到节点多的上面。

下面我们来实现优化后的代码：

public class UnionFind3 implements UF{
    private int[] parent;
    // sz[i] 表示以 i 为根的集合中元素个数
    private int[] sz;
    public UnionFind3(int size) {
        parent = new int[size];
        sz = new int[size];
        for (int i = 0; i < size; i++) {
            // parent[i] 表示的是第 i 个元素所在的节点指向了哪个元素
            parent[i] = i;
            sz[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    private int find(int p) {
        if (p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is not bound.");

        while (p != parent[p])
            p = parent[p];
        return p;
    }

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

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        // 根据两个元素所在树的元素个数不同判断合并方向，将元素个数少的集合合并到元素个数多的集合上
        if (sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else {
            parent[qRoot] = pRoot;
            sz[pRoot]+= sz[qRoot];
        }
    }
}

在 main 函数中添加如下代码

UnionFind3 uf3 = new UnionFind3(size);
System.out.println("UnionFind3：" + testUF(uf3, m) + "s");

运行程序，打印结果如下：

UnionFind1：5.652589518s
UnionFind2：9.922453961s
UnionFind3：0.013820609s

可以看到基于 size 优化后的并查集性能提高了很多。

基于rank的优化

经过上面的代码优化，代码的性能是得到了很大提升，但是还存在一些问题。比如下面这两个集合按照上面的操作合并的话，合并后得到的树高度明显增加了。而我们代码的时间复杂度是和树的高度密切相关的，所以明显还需要优化。
Snip20220128_123.png
我们可将高度低的树合并到高度高的树上面，从而降低合并后树的高度：
Snip20220128_124.png
下面我们使用一个 rank 数组来记录树的层数也就是高度，再次对代码进行优化：

public class UnionFind4 implements UF {
    private int[] parent;
    private int[] rank; // rank[i] 表示以 i 为根的集合所表示的树的层数
    public UnionFind4(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
            // 每个树的初始高度为 1
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }
    private int find(int p) {
        if (p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is not bound.");

        while (p != parent[p])
            p = parent[p];
        return 1;
    }
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        // 根据两个元素所在树的 rank 不同判断合并方向
        // 将 rank 低的集合合并到 rank 高的集合上
        if (rank[pRoot] < rank[qRoot])
            parent[pRoot] = qRoot;
        else if (rank[qRoot] < rank[pRoot])
            parent[qRoot] = pRoot;
        else {
            // 如果两个树的高度相等的话，谁合并到谁都是可以的，但是相应的合并后的树的高度要加 1
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }
    }
}

Main.java 文件中加入以下代码：

UnionFind4 uf4 = new UnionFind4(size);
System.out.println("UnionFind4：" + testUF(uf4, m) + "s");

运行程序：

UnionFind1：5.553888942s
UnionFind2：9.927654271s
UnionFind3：0.013719365s
UnionFind4：0.006136891s

可以看到，经过优化后，代码的执行时间得到了较大提升。

路径压缩

合并后的树可以有很多中不同的表示方法：
Snip20220129_125.png
通过上面的学习我们知道对于并查集的的相关操作的时间复杂度是和树的高度密切相关的，所以我们最理想的状态是每个树的合并最好都合并成图上红色的树那样。但实际开发中将所有的合并操作都整理成图上红色的树那样还是比较难的。但我们可以在操作的过程中适当降低树的高度，由于并查集的操作基本都设计到了 find 操作，所以我们对 find 方法进行优化，在这个方法里实现路径压缩。我们可以在 find() 方法中插入以下代码：

parent[p]=parent[parent[p]]

这行代码也比较好理解，说白了就是将 p 的父节点设置为 p 的父节点的父节点，从而达到路径压缩的目的。下面我们来看代码的具体实现：

public class UnionFind5 implements UF {
    private int[] parent;
    private int[] rank; // rank[i] 表示以 i 为根的集合所表示的树的层数
    public UnionFind5(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }
    private int find(int p) {
        if (p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is not bound.");

        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        // 根据两个元素所在树的 rank 不同判断合并方向
        // 将 rank 低的集合合并到 rank 高的集合上
        if (rank[pRoot] < rank[qRoot])
            parent[pRoot] = qRoot;
        else if (rank[qRoot] < rank[pRoot])
            parent[qRoot] = pRoot;
        else {
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }
    }
}

可以看到，在上面的优化过程中我们只修改了 find 里面的代码，在执行查找操作的时候降低树的高度，但是在合并的时候我们并没有对 rank 进行相应的递减操作，这样 rank 表示的数据不就不准了吗？是的，rank 所表示的数据会不是很准，但是我们没有必须对 rank 进行操作，这里的 rank 仅当做一个参考即可。在数据量很大的时候，相应调整 rank 也是会消耗不少性能的。

main函数改写如下：

public static void main(String[] args) {
    int m = 10000000;
    int size = 10000000;

    UnionFind4 uf4 = new UnionFind4(size);
    System.out.println("UnionFind4：" + testUF(uf4, m) + "s");
    UnionFind5 uf5 = new UnionFind5(size);
    System.out.println("UnionFind5：" + testUF(uf5, m) + "s");
}

运行程序结果如下：

UnionFind4：2.325940223s
UnionFind5：1.990184511s

可以看到经过路径压缩后代码性能又得到了不错的提升。顺便说下，为什么我们在 main 函数中去掉前三种的测试代码，这是因为我们将测试数据量加的很大，前三种的性能相对差很多，如果不去掉的话，程序要运行很久才能看到结果。

更多和并查集相关的话题

我们可以使用递归在查找的时候将树调整成下面这样：
Snip20220129_129.png

public class UnionFind6 implements UF {
    private int[] parent;
    private int[] rank;

    public UnionFind6(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = i;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    private int find(int p) {
        if (p <= 0 || p > parent.length)
            return -1;

        if (p != parent[p])
            // find(parent[p]) 返回 p 的父节点所对应的根节点是谁
            parent[p] = find(parent[p]);

        return parent[p];
    }

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

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        if (rank[pRoot] < rank[qRoot])
            parent[pRoot] = qRoot;
        else if (rank[qRoot] < rank[pRoot])
            parent[qRoot] = pRoot;
        else {
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;
        }
    }
}

修改 Main.java 文件中的代码如下：

public static void main(String[] args) {
        int m = 10000000;
        int size = 10000000;
        UnionFind5 uf5 = new UnionFind5(size);
        System.out.println("UnionFind5：" + testUF(uf5, m) + "s");
        UnionFind6 uf6 = new UnionFind6(size);
        System.out.println("UnionFind6：" + testUF(uf6, m) + "s");
    }

测试结果如下：

UnionFind5：3.929333751s
UnionFind6：3.819205885s

从测试结果可以看出，代码性能提升并不是特别的明显。运行的次数多的时候，还可能出现这一版比上一版慢一点点的情况，这是因为这版的路径压缩过程我们使用了递归，递归肯定是要浪费些性能的。

并查集的时间复杂度理论来说是 O(log*n) ，比 O(logn) 要小，近乎是 O(1) 级别的。