数据结构与算法 / 系统课时
路径压缩与按秩合并
路径压缩与按秩合并
并查集的基本操作并不复杂,真正决定性能的是树如何生长。本课用路径压缩缩短查找链,再用按秩合并避免高树挂到矮树上,最终把大量连续查询与合并的摊还成本降到几乎常数级。
学习目标
- 解释路径压缩与按秩合并分别解决什么问题。
- 正确实现
find、union和连通性查询。 - 分析两种优化组合后的摊还复杂度与边界。
核心原理与执行过程
并查集把每个集合表示成一棵有根树,parent[x] 指向节点 x 的父节点,根节点满足 parent[x] == x。两个元素属于同一集合,当且仅当它们最终找到同一个根。
路径压缩
普通 find(x) 会沿父指针一直走到根。路径压缩在返回根时,把沿途节点直接改为指向根。第一次查找可能仍需经过多层,但之后再查同一路径时会明显更短。
按秩合并
合并两个集合时,先分别找到根。若根不同,就把秩较小的根连接到秩较大的根;只有两棵树秩相同时,才任选一个根作为新根并把它的秩加一。这里的 rank 是树高上界的近似记录,路径压缩后不必同步减小。

| 优化策略 | 修改时机 | 主要作用 | 必须维护的信息 |
|---|---|---|---|
| 路径压缩 | 执行 find 时 |
缩短以后查找的父指针链 | parent |
| 按秩合并 | 执行 union 时 |
防止树在合并阶段快速变高 | parent、rank |
复杂度与边界
同时使用两种优化后,包含 次操作、 个元素的总时间为 ,单次操作的摊还复杂度为 。反阿克曼函数 增长极慢,在实际可处理的数据规模内通常不超过一个很小的常数,但它并不是严格的 。
初始化需要 时间和 空间。元素下标必须位于 0 到 n - 1;合并前必须先取根,不能直接比较或修改任意节点的 rank。
完整可运行示例
下面的 Java 17 程序先构造一棵具有多层父指针的集合,再对节点 7 执行查找,观察路径压缩前后的数组变化。
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));
}
}运行命令:
javac UnionFindOptimizationDemo.java
java UnionFindOptimizationDemo预期输出
压缩前: [0, 0, 0, 2, 0, 4, 4, 6]
find(7) 的根: 0
压缩后: [0, 0, 0, 2, 0, 4, 0, 0]
3 与 7 连通: trueTips、常见错误与练习
- 在
find中必须保存递归返回的根,即写成parent[x] = find(parent[x]);只调用递归而不赋值,不会产生路径压缩。 rank只对根有意义。把普通节点的rank用作合并依据,会破坏树高控制策略。- 递归版
find简洁可靠;若运行环境栈深度受限,可以改成两次循环:第一次找到根,第二次压缩路径。
练习 1:为示例增加 componentCount,初始化为元素总数,仅在两个不同集合真正合并时减一。验收条件是重复执行同一合并不会再次减少计数。
练习 2:实现迭代版路径压缩,并用随机操作对比递归版的根结果。验收条件是两种实现对每个元素返回相同根,且压缩后所有被访问节点都直接或更近地指向根。
本课总结
- 路径压缩优化查找过程,按秩合并优化树的生成过程。
- 两种策略组合后,连续操作的摊还复杂度为 。
rank只在根之间比较,路径压缩后不需要按真实树高回退。
下一课预告
下一阶段可以把并查集用于图的连通分量、最小生成树和动态连通性问题,重点关注如何把业务关系映射为合并与查询操作。