数据结构与算法 / 系统课时

路径压缩与按秩合并

路径压缩与按秩合并

并查集的基本操作并不复杂,真正决定性能的是树如何生长。本课用路径压缩缩短查找链,再用按秩合并避免高树挂到矮树上,最终把大量连续查询与合并的摊还成本降到几乎常数级。

学习目标

  • 解释路径压缩与按秩合并分别解决什么问题。
  • 正确实现 find、union 和连通性查询。
  • 分析两种优化组合后的摊还复杂度与边界。

核心原理与执行过程

并查集把每个集合表示成一棵有根树,parent[x] 指向节点 x 的父节点,根节点满足 parent[x] == x。两个元素属于同一集合,当且仅当它们最终找到同一个根。

路径压缩

普通 find(x) 会沿父指针一直走到根。路径压缩在返回根时,把沿途节点直接改为指向根。第一次查找可能仍需经过多层,但之后再查同一路径时会明显更短。

按秩合并

合并两个集合时,先分别找到根。若根不同,就把秩较小的根连接到秩较大的根;只有两棵树秩相同时,才任选一个根作为新根并把它的秩加一。这里的 rank 是树高上界的近似记录,路径压缩后不必同步减小。

路径压缩与按秩合并前后结构

优化策略 修改时机 主要作用 必须维护的信息
路径压缩 执行 find 时 缩短以后查找的父指针链 parent
按秩合并 执行 union 时 防止树在合并阶段快速变高 parent、rank

复杂度与边界

同时使用两种优化后,包含 mm 次操作、nn 个元素的总时间为 O(mα(n))O(m\alpha(n)),单次操作的摊还复杂度为 O(α(n))O(\alpha(n))。反阿克曼函数 α(n)\alpha(n) 增长极慢,在实际可处理的数据规模内通常不超过一个很小的常数,但它并不是严格的 O(1)O(1)。

初始化需要 O(n)O(n) 时间和 O(n)O(n) 空间。元素下标必须位于 0 到 n - 1;合并前必须先取根,不能直接比较或修改任意节点的 rank。

完整可运行示例

下面的 Java 17 程序先构造一棵具有多层父指针的集合,再对节点 7 执行查找,观察路径压缩前后的数组变化。

java
import java.util.Arrays;

public class UnionFindOptimizationDemo {

    static final class UnionFind {
        private final int[] parent;
        private final int[] rank;

        UnionFind(int size) {
            if (size <= 0) {
                throw new IllegalArgumentException("size must be positive");
            }
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        int find(int x) {
            checkIndex(x);
            if (parent[x] != x) {
                // 回溯时让沿途节点直接指向根。
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        boolean union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);
            if (rootA == rootB) {
                return false;
            }

            // 低秩树挂到高秩树下;秩相同才增加新根的秩。
            if (rank[rootA] < rank[rootB]) {
                parent[rootA] = rootB;
            } else if (rank[rootA] > rank[rootB]) {
                parent[rootB] = rootA;
            } else {
                parent[rootB] = rootA;
                rank[rootA]++;
            }
            return true;
        }

        boolean connected(int a, int b) {
            return find(a) == find(b);
        }

        int[] snapshotParents() {
            return Arrays.copyOf(parent, parent.length);
        }

        private void checkIndex(int x) {
            if (x < 0 || x >= parent.length) {
                throw new IndexOutOfBoundsException("invalid index: " + x);
            }
        }
    }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(8);

        uf.union(0, 1);
        uf.union(2, 3);
        uf.union(4, 5);
        uf.union(6, 7);
        uf.union(0, 2);
        uf.union(4, 6);
        uf.union(0, 4);

        System.out.println("压缩前: " + Arrays.toString(uf.snapshotParents()));
        System.out.println("find(7) 的根: " + uf.find(7));
        System.out.println("压缩后: " + Arrays.toString(uf.snapshotParents()));
        System.out.println("3 与 7 连通: " + uf.connected(3, 7));
    }
}

运行命令:

bash
javac UnionFindOptimizationDemo.java
java UnionFindOptimizationDemo

预期输出

text
压缩前: [0, 0, 0, 2, 0, 4, 4, 6]
find(7) 的根: 0
压缩后: [0, 0, 0, 2, 0, 4, 0, 0]
3 与 7 连通: true

Tips、常见错误与练习

  • 在 find 中必须保存递归返回的根,即写成 parent[x] = find(parent[x]);只调用递归而不赋值,不会产生路径压缩。
  • rank 只对根有意义。把普通节点的 rank 用作合并依据,会破坏树高控制策略。
  • 递归版 find 简洁可靠;若运行环境栈深度受限,可以改成两次循环:第一次找到根,第二次压缩路径。

练习 1:为示例增加 componentCount,初始化为元素总数,仅在两个不同集合真正合并时减一。验收条件是重复执行同一合并不会再次减少计数。

练习 2:实现迭代版路径压缩,并用随机操作对比递归版的根结果。验收条件是两种实现对每个元素返回相同根,且压缩后所有被访问节点都直接或更近地指向根。

本课总结

  • 路径压缩优化查找过程,按秩合并优化树的生成过程。
  • 两种策略组合后,连续操作的摊还复杂度为 O(α(n))O(\alpha(n))。
  • rank 只在根之间比较,路径压缩后不需要按真实树高回退。

下一课预告

下一阶段可以把并查集用于图的连通分量、最小生成树和动态连通性问题,重点关注如何把业务关系映射为合并与查询操作。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

路径压缩与按秩合并

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通