第 21 章 不相交集合数据结构 (Data Structures for Disjoint Sets)
核心结论
-
三种操作：MAKE-SET(x) 建单元素集；UNION(x,y) 合并两个集合；FIND-SET(x) 返回 x 所在集合的代表元；m 次操作总时间用 O(m α(n))（n = MAKE-SET 次数，α = 反 Ackermann 函数）。
-
链表表示 + 加权合并：链表头指针 + 表长度启发式 → 总成本 O(m + n lg n)；简单但仅 O(m lg n) 摊还。
-
不相交集合森林 + 两个启发式：每个元素只有指向父的指针；union by rank（小根并入大根）+ path compression（find 时直接挂到根）→ 摊还 O(α(n))。
-
路径压缩不改变 rank：rank 是「节点高度上界」，压缩只是减少路径长度、保留相对关系。
-
反 Ackermann 函数 α(n)：极慢增长 — α(n) ≤ 4 对「宇宙中原子数 n 仍成立」；O(m α(n)) 在工程上可视为线性。
-
实际应用：Kruskal MST（第 23 章）、连通分量、Tarjan LCA、offline LCA、并查集实现 LRU 替换（如 ARC、2Q 的 victim 候选）。
|
本章主旨
本章是「最实用的渐近快」数据结构代表——不相交集合森林（disjoint-set forest）。它用 union by rank + path compression 把每个操作摊还到 α(n)（一种极慢增长函数，n 宇宙原子数时仍 ≤ 4），工程上几乎等价于 O(1)。章内三节：21.1 介绍问题与最朴素的应用（动态连通分量）；21.2 给出简单但慢的链表实现作为反衬；21.3-21.4 介绍最快的森林实现并以精妙的势能分析证明 O(m α(n)) 上界。本章的势能函数设计（按 rank 分层 + level + iter 二维节点势）是 CLRS 最精巧的分析之一，与第 19 章斐波那契堆的「size ≥ F_{k+2} ≥ φ^k」对照阅读，能体会到「不动点分析」的统一美感。 |
一、核心概念
本章围绕 5 个核心概念展开：先建立不相交集合抽象（21.1）与应用（连通分量），再深入链表实现（21.2），最后进入森林 + 两个启发式（21.3）与势能分析（21.4）。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
不相交集合 ADT |
MAKE-SET / UNION / FIND-SET 三操作；UNION 销毁两个原集合，FIND-SET 返回代表元。 |
§21.1;CONNECTED-COMPONENTS(G) 处理每条边：FIND-SET 判断是否同集，否则 UNION。 |
链表实现 + 朴素 UNION |
每集 = 带头尾指针的链表；朴素 UNION 把短链表接到长表尾 → 单次 O(n)；n 次 MAKE+UNION 共 Θ(n²)。 |
§21.2;CLRS 图 21.3 给出最坏 Θ(n²) 例子。 |
链表实现 + 加权 UNION 启发式 |
每集存表长度，总是把「短表」接到「长表」尾；总成本 O(m + n lg n)。 |
§21.2 定理 21.1;每个对象的 set 指针最多改 ⌊lg n⌋ 次。 |
不相交集合森林 |
每元素 = 节点带 p 指针；多棵树用 root 表示各集合；UNION 让 root 互指。 |
§21.3;非最坏分析同链表，但加启发式后飞跃。 |
Union by Rank + Path Compression |
rank = 节点高度上界；UNION 小 rank 挂大 rank；FIND-SET 递归访问时把路径上的节点直接指向根。 |
§21.3 伪代码（MAKE-SET/UNION/LINK/FIND-SET）;组合后摊还 O(α(n))。 |
二、详细笔记
2.1 不相交集合操作与连通分量
What：不相交集合维护动态集合族 S = {S₁, S₂, …, Sk}；每个集合有一个「代表元」；操作 MAKE-SET、UNION、FIND-SET 三种；m 次操作总时间用参数 n（MAKE-SET 次数）和 m（操作总数）。
Why：动态连通分量是最朴素的应用——图加边时合并两个端点所在的集合；查询两顶点是否连通 = 检查 FIND-SET 是否同代表。
How：
| 操作 | 实现 | 时间 |
|---|---|---|
MAKE-SET(x) |
新建单节点集合 |
O(1) |
UNION(x, y) |
销毁两集合，建立 Sₓ ∪ Sᵧ |
O(1) 调用 + 两个 FIND-SET |
FIND-SET(x) |
返回 x 所在集合的代表元 |
沿父指针走 |
CONNECTED-COMPONENTS(G) |
MAKE-SET 每个顶点；按边遍历，FIND-SET 不同则 UNION |
When：动态加边查询连通性；Kruskal（23.2）需要 union-find 维护跨边连通性；offline LCA、Union-Find 类应用皆用此结构。
Example：CLRS 图 21.1 —— 4 连通分量 {a,b,c,d}、{e,f,g}、{h,i}、{j}；处理边 (b,d)、(e,g)、(a,c)、(h,i)、(a,b)、(e,f)、(b,c) 后合并为 3 个连通分量。
2.2 链表表示
What：每个集合 = 带头尾指针的链表；链表中每元素含「指向集合对象」的指针；朴素 UNION 把短链表接到长表尾并更新短链表的 set 指针。
Why：作为「最慢但简单」的对照基线——朴素 UNION 最坏 Θ(n²)（CLRS 图 21.3）；加权 UNION（按表长合并短表）改进到 O(m + n lg n)；但仍不如森林+两个启发式。
How：
| 表示 | MAKE-SET |
|---|---|
FIND-SET |
UNION（朴素） |
UNION（加权） |
链表 + set 指针 |
O(1) |
跟随 set 指针 + 头指针 |
短表接长表尾 → 更新每个 set 指针 → Θ(n) |
仅当「短表」接到「长表」尾时交换 → 每次更新 ≤ ⌊lg n⌋ 元素 |
总成本 |
O(m) |
O(m) |
Θ(n²)（图 21.3） |
When：当操作类型仅 MAKE-SET + FIND-SET、UNION 极少时——链表足够；否则用森林。
Example：连续 UNION(x_{i+1}, x_i) 序列下朴素 UNION 总复制成本 1+2+…+(n−1) = Θ(n²)；加权和改为 2^{⌊lg n⌋} 增长。
2.3 不相交集合森林（带两个启发式）
What：每节点仅有 p（父指针）；操作 FIND-SET 沿父链到根；UNION 让 root 互指 + 启发式。
Why：路径压缩直接缩短「下次 FIND-SET」的路径；union by rank 限制树高；二者的精确组合给出 α(n) 摊还。
How：
| 启发式 | 规则 |
|---|---|
效果 |
Union by rank |
维护 rank（高度上界）；UNION 让小 rank 的 root 指向大 rank 的 root；等则后者作父并 rank++ |
限制树高 O(lg n)（单独） |
Path Compression |
FIND-SET(x) 时把路径上每个节点直接挂到根（递归式：x.p = FIND-SET(x.p); return x.p） |
大幅缩短后续 FIND-SET 路径 |
组合 |
两者并存 |
总摊还 O(α(n)) |
关键伪代码：
-
MAKE-SET(x): x.p = x; x.rank = 0
-
UNION(x, y): LINK(FIND-SET(x), FIND-SET(y))
-
LINK(x, y): 若 x.rank > y.rank: y.p = x；else x.p = y；若等则 y.rank++
-
FIND-SET(x): 若 x ≠ x.p: x.p = FIND-SET(x.p); return x.p
When：任何需要 union-find 的场景——Kruskal、Tarjan LCA、Borůvka MST、离线 LCA、并查集式 LRU 候选替换。
Example：FIND-SET 在经过反复访问后，整棵树变得扁平——根到所有节点的路径几乎为 2 跳（根 → 节点 → 根）。
2.4 Ackermann 函数与其反函数 α
What：Ackermann 函数 \(A_k(j)\) 极快增长（k=1: 2j+1；k=2: 2^{j+1}(j+1)−1；k=3: 2{2{…}} 极深叠加；k=4: 已超宇宙原子数）；α(n) = min{k : A_k(1) ≥ n} 是其「极慢」反函数。
Why：α(n) 是 union-find 摊还界的真正「罪魁」——其慢增长让 O(m α(n)) 在所有可想象 n 下 ≤ 5m，对工程而言即为线性。
How：
具体值（CLRS §21.4）：
| n | α(n) |
|---|---|
0 ≤ n ≤ 2 |
0 |
n = 3 |
1 |
4 ≤ n ≤ 7 |
2 |
8 ≤ n ≤ 2047 |
3 |
2048 ≤ n ≤ A₄(1) ≈ 10⁸⁰ |
4 |
When：理解为何 O(m α(n)) 几乎等于 O(m)；n = 宇宙原子数 ≈ 10⁸⁰ 时 α(n) = 4；n 须超 A₄(1) 才让 α(n) = 5。
Example：A₁(j) = 2j+1 → A₁(1) = 3；A₂(j) = 2^{j+1}(j+1)−1 → A₂(1) = 7；A₃(1) = 2047；A₄(1) > 10⁸⁰（远大于可观测宇宙原子数）。
2.5 势能分析 O(m α(n))
What：总势能 χ_q = Σₓ φ_q(x)，其中节点势由「level(x) + iter(x)」决定；操作摊还 ≤ cost + Δχ；最终总摊还 ≤ O(m α(n))。
Why：union-find 的 α(n) 界证明是 CLRS 最复杂的势能分析之一——用「rank 分层 + 每层贡献 α」的精妙结构证明每个操作均摊 O(α(n))。
How：
| 分析要素 | 定义 / 范围 |
|---|---|
x.rank |
节点高度上界；Lemma 21.6：x.rank ≤ n−1 |
A_k(j) |
Ackermann 函数；A₀(j)=j+1；A₁(j)=2j+1；A₂(j)=2^{j+1}(j+1)−1 |
α(n) |
min{k : A_k(1) ≥ n} ≤ 4 (对可观测 n) |
level(x) |
max{k : x.p.rank ≥ A_k(x.rank)} (x 不是 root, rank > 0) |
iter(x) |
max{i : x.p.rank ≥ A_{level(x)}^{(i)}(x.rank)} |
φ(x) |
(α(n) − level(x))·x.rank − iter(x)，否则 α(n)·x.rank |
χ(H) = Σₓ φ_q(x) |
总势能 |
关键引理：
-
Lemma 21.4：x.rank ≤ x.p.rank（严格若 x ≠ x.p）
-
Lemma 21.6：x.rank ≤ n − 1
-
Lemma 21.8：0 ≤ φ_q(x) ≤ α(n)·x.rank
-
Lemma 21.10：FIND-SET 与 LINK 摊还 ≤ O(α(n))
When：理解 union-find 的内部「为什么这么快」；也是学习「势能分析精密化」的最佳案例。
Example：FIND-SET 沿路径「释放」势能（缩短路径）→ Δχ ≤ α(n) − Σpath iter；总摊还 O(α(n))。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 21 章 不相交集合))
ADT
MAKE-SET
UNION
FIND-SET
应用
连通分量
Kruskal
Tarjan LCA
链表实现
朴素O(n2)
加权O(mlgn)
森林实现
节点p指针
多棵树
启发式
Union by rank
Path compression
摊还O(α(n))
复杂度分析
Ackermann函数
反函数α(n)慢增长
α(n)≤4实用
势能函数
level(x)
iter(x)
φ(α-level)r-iter
== 五、重点与易错点
. union-find 是「最实用快」数据结构——摊还 α(n) 对工程几乎等价 O(1)；首选实现。
. 朴素链表 + 朴素 UNION 是 Θ(n²) 反例（图 21.3）；一定要用加权 UNION 或森林。
. 「代表元」是某个具体的成员元素，不一定是 id 最小——链表头元素或森林根。
. UNION 在不相交集合 ADT 中销毁两集合，但实现上常保留只更新指针——这不改变 ADT 语义。
. Path Compression 让 x 的父直接指向根，但 rank 不变 — rank 是「曾孙可能高度上界」，不是当前高度。
. 单独 Union by rank 给出 O(m lg n) 最坏摊还（习题 21.4-4）— 单独不够；必须配 PC。
. 单独 Path Compression 给出 O(m + f·lg(1+f/n)·n) (CLRS 式 21.7) — 已接近线性但仍带 lg 项；与 rank 组合降到 α(n)。
. α(n) 实际上限：n ≤ 可观测宇宙原子数 ≈ 10⁸⁰ 时 α(n) ≤ 4 — 工程上 α(n) 总看作常数。
. Ackermann 函数 A_k(j) 在 k ≥ 2 时已爆炸增长 — 势能分析中用它构造「level 渐增、iter 渐小」的精妙结构。
. UNION 实现细节：先做两个 FIND-SET 取代表元，再 LINK(root1, root2)；LINK 只在 root 上操作 — 普通节点的父不直接 LINK。
. 实践中 union-find 常作为「Kruskal 的辅助结构」——边按权重扫描，用 union-find 检查「是否跨连通分量」，决定是否加入 MST。
. union-find 不支持分裂/拆分集合——删除元素只能「走后再重建」；这是它的限制。
. Tarjan LCA 算法（CLRS 问题 21-3）使用 union-find 的变体——给每个节点按深度分配时间戳 + ancestor 标志。
. union-find 的「实现选择」：递归 vs. 尾递归（栈深度）；循环 + 路径压缩的迭代版本更稳定。
. 节点数 n = MAKE-SET 数 ≤ 总操作数 m；这是复杂度分析中两个参数的关系。