第 3 版 quick-union 基于 size 的优化

我们发现 union(4, 9) 与 union(9, 4) 其实是一样的，也就是把谁的根指向谁的根，这一点从正确性上来说是无关紧要的，但是对于 find 的时间复杂度就会有影响。为此，我们做如下优化。

在合并之前做判断，具体做法是，计算每一个结点有多少个元素直接或者间接地以它为根，我们应该将集合元素少的那结点的根指向集合元素多的那个结点的根。这样，形成的树就会更高概率地形成一棵层数较低的树。

为此，我们再引入一个 size 数组，size[i] 的定义是：以第 i 个结点为根的集合的元素的个数。

在初始化的时候 size[i] = 1，find 和 isConnected 操作中我们都不须要去维护 size 这个数组，唯独在 unionElements 的时候，我们才要维护 size 数组的定义。

Java 代码：

// 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 isConnected(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--;
    }
}

---

作者：liweiwei1419 链接：https://suanfa8.com/union-find/quick-union-optimization-size 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。