第 6 版 quick-union 基于路径压缩的递归实现

重点提示：这一节重要。

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

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

Java 代码：

/**
 * 返回索引为 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 数组的当前实现仍然可以作为一个参考值，比起随机的做法要更有意义一些。

其实写到这里，数组 rank 还是数组 size 的意义都不太重要了，我们只须要在 find 的时候，做好路径压缩，把孩子结点指向父亲结点即可。

---

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