cover.png#最小生成树与并查集

可以参考集合与图论和数据结构（H）两门课的笔记，个人认为 CLRS 在图论方面的名词翻译有点奇怪

图的表示

图 \(G = (V, E)\)，\(V\) 为顶点集，\(E\) 为边集（\(E \subseteq V \times V\)）

图可以是有向的或无向的。假设 \(V = \{1, 2, \ldots, n\}\)

邻接矩阵

定义 \(A[1..n, 1..n]\)：

\[A[i,j] = \begin{cases} 1 & (i,j) \in E \\ 0 & (i,j) \notin E \end{cases}\]

空间 \(\Theta(V^2)\)，适合稠密图

无向图的邻接矩阵是对称的：\(A[i,j] = A[j,i]\)

邻接表

对每个顶点 \(v\)，维护邻接链表 \(\text{Adj}[v]\)

空间 \(\Theta(V + E)\)，适合稀疏图

对无向图：\(|\text{Adj}[v]| = \deg(v)\)

握手引理：\(\sum_{v \in V} \deg(v) = 2|E|\)

比较

操作	邻接矩阵	邻接表
空间	\(\Theta(V^2)\)	\(\Theta(V + E)\)
检查 \((u,v) \in E\)	\(O(1)\)	\(O(\deg(u))\)
遍历 \(u\) 的邻居	\(O(V)\)	\(O(\deg(u))\)
添加边	\(O(1)\)	\(O(1)\)
删除边	\(O(1)\)	\(O(\deg(u))\)

若图是连通的：\(|E| \geq |V| - 1\)，因此 \(\lg|E| = \Theta(\lg V)\)

---

最小生成树 (MST)

输入：无向连通图 \(G = (V, E)\)，权重函数 \(w: E \to \mathbb{R}\)

生成树：连接所有顶点的无环连通子图，恰好 \(|V|-1\) 条边

最小生成树：权重之和 \(w(T) = \sum_{(u,v) \in T} w(u,v)\) 最小的生成树

最优子结构

设 \(T\) 是 \(G\) 的 MST，移除边 \((u,v) \in T\) 将 \(T\) 分为 \(T_1\) 和 \(T_2\)

性质：\(T_1\) 是由 \(T_1\) 中顶点导出的子图 \(G_1\) 的 MST，\(T_2\) 同理

点击查看证明

\(w(T) = w(u,v) + w(T_1) + w(T_2)\)

反证：若 \(T_1\) 不是 \(G_1\) 的 MST，存在更好的 \(T_1'\)，则 \(T' = T_1' \cup \{(u,v)\} \cup T_2\) 是 \(G\) 的生成树且 \(w(T') < w(T)\)，与 \(T\) 是 MST 矛盾

---

通用 MST 算法 (CLRS 23.1)

CLRS 用一个统一的框架描述所有 MST 算法

割、轻边与安全边

割 (Cut)：将 \(V\) 分为 \(S\) 和 \(V \setminus S\) 两部分的划分 \((S, V \setminus S)\)

跨越割的边：一个端点在 \(S\)，另一个在 \(V \setminus S\)

尊重 (respect) 集合 \(A\)：\(A\) 中没有边跨越割 \((S, V \setminus S)\)

轻边 (light edge)：跨越割的最小权边

安全边 (safe edge)：加入集合 \(A\) 后 \(A\) 仍是某个 MST 子集的边

通用算法

GENERIC-MST(G, w):
    A ← ∅
    while A 不是生成树:
        找 A 的一条安全边 (u,v)
        A ← A ∪ {(u,v)}
    return A

不变量：每次循环前，\(A\) 是某个 MST 的子集

这一块图论内容建议参考图论相关笔记

安全边定理 (CLRS Theorem 23.1)

定理：设 \(G = (V, E)\) 为无向连通加权图，\(A \subseteq E\) 是某个 MST 的子集，\((S, V \setminus S)\) 是尊重集合 \(A\) 的任意割，\((u,v)\) 是跨越该割的轻边。则 \((u,v)\) 对 \(A\) 是安全的

点击查看证明

设 \(T\) 是包含 \(A\) 的 MST

情况 1：\((u,v) \in T\)。则 \(A \cup \{(u,v)\} \subseteq T\)，\((u,v)\) 对 \(A\) 安全

情况 2：\((u,v) \notin T\)

在 \(T\) 中 \(u\) 到 \(v\) 有唯一路径 \(p\)。由于 \(u \in S\)，\(v \in V \setminus S\)，路径 \(p\) 必至少跨越割一次

设 \((x,y)\) 是路径 \(p\) 上跨越割的一条边（\(x \in S\), \(y \in V \setminus S\)）

由于割尊重 \(A\)：\((x,y) \notin A\)

构造 \(T' = T \setminus \{(x,y)\} \cup \{(u,v)\}\)

\(T'\) 是生成树：移除 \((x,y)\) 将 \(T\) 分为两棵子树，\((u,v)\) 重新连接它们（\(u, v\) 分别在两侧）

\(T'\) 的权重：\(w(T') = w(T) - w(x,y) + w(u,v) \leq w(T)\)

因为 \((u,v)\) 是跨越割的轻边，\(w(u,v) \leq w(x,y)\)

所以 \(T'\) 也是 MST

\(A \cup \{(u,v)\} \subseteq T'\)（\(A \subseteq T\) 且 \(A\) 不含 \((x,y)\)，所以 \(A \subseteq T \setminus \{(x,y)\} \subset T'\)）

因此 \((u,v)\) 对 \(A\) 安全

推论 (CLRS Corollary 23.2)：设 \(G = (V,E)\) 为连通加权图，\(A\) 是某 MST 子集，\(C = (V_C, E_C)\) 是 \(G_A = (V, A)\) 的一个连通分量。若 \((u,v)\) 是连接 \(C\) 与其他连通分量的轻边，则 \((u,v)\) 对 \(A\) 安全

点击查看证明

取割 \((S, V \setminus S)\) 使得 \(S = V_C\)。由于 \(A\) 的每条边两端点在同一连通分量中，割尊重 \(A\)。\((u,v)\) 是跨越此割的轻边，由定理 23.1，\((u,v)\) 安全

割性质与环性质

安全边定理是 MST 理论的核心，蕴含两个性质：

割性质 (Cut Property)：对于尊重当前边集的任意割，跨越该割的唯一最小权边必在每个 MST 中

环性质 (Cycle Property)：对于图中任意环，环上的唯一最大权边不在任何 MST 中

点击查看环性质证明

设 \(e = (u,v)\) 是环 \(C\) 上权重最大的边（且唯一最大），假设 \(e \in T\)（\(T\) 是 MST）

移除 \(e\) 将 \(T\) 分为 \(T_1\) 和 \(T_2\)，\(u \in T_1\), \(v \in T_2\)

环 \(C\) 中必有另一条边 \(e' = (x,y)\) 跨越 \((T_1, T_2)\)（环必须绕回来）

\(T' = T \setminus \{e\} \cup \{e'\}\) 是生成树，\(w(T') = w(T) - w(e) + w(e') < w(T)\)

矛盾于 \(T\) 是 MST

---

Kruskal 算法 (CLRS 23.2)

按边权从小到大考虑每条边，只要不形成环就加入

算法

KRUSKAL(G, w):
    A ← ∅
    for each v ∈ V:
        MAKE-SET(v)
    按 w 非递减排序所有边
    for each (u,v) ∈ E（按权重递增）:
        if FIND-SET(u) ≠ FIND-SET(v):
            A ← A ∪ {(u,v)}
            UNION(u, v)
    return A

正确性 (CLRS)

每次加入的边 \((u,v)\) 连接两个不同的连通分量

设 \(C_u\) 为包含 \(u\) 的连通分量，取割 \((C_u, V \setminus C_u)\)

\(A\) 中没有边跨越此割（否则 \(C_u\) 和对面分量应已合并），割尊重 \(A\)

\((u,v)\) 是跨越此割的边，且是当前排序中最小的（之前的跨割边已被考虑过——它们要么被加入 \(A\)（此时两端已在同一分量），要么不跨越此割）

实际上 \((u,v)\) 就是跨越此割的轻边：所有权重更小的边要么不跨越此割，要么已使两端合并

由推论 23.2，\((u,v)\) 对 \(A\) 安全

详细示例

初始集合: {A}, {B}, {C}, {D}, {E}, {F}, {G}, {H}

排序后的边:
(B,E):2, (F,G):3, (A,B):4, (G,H):5, (A,H):6, (B,G):8, (C,G):9, (A,G):10, (C,D):14, (D,F):15

加入 (B,E):2 → {A}, {B,E}, {C}, {D}, {F}, {G}, {H}
加入 (F,G):3 → {A}, {B,E}, {C}, {D}, {F,G}, {H}
加入 (A,B):4 → {A,B,E}, {C}, {D}, {F,G}, {H}
加入 (G,H):5 → {A,B,E}, {C}, {D}, {F,G,H}
加入 (A,H):6 → {A,B,E,F,G,H}, {C}, {D}
跳过 (B,G):8 （同一集合）
加入 (C,G):9 → {A,B,C,E,F,G,H}, {D}
跳过 (A,G):10 （同一集合）
加入 (C,D):14 → {A,B,C,D,E,F,G,H}
跳过 (D,F):15 （同一集合）

MST 边集：\(\{(B,E), (F,G), (A,B), (G,H), (A,H), (C,G), (C,D)\}\)

总权重：\(2 + 3 + 4 + 5 + 6 + 9 + 15 = 43\)

共 \(|V| - 1 = 7\) 条边

时间复杂度

• 排序：\(O(E \log E)\)
• \(2|E|\) 次 FIND-SET + \(|V| - 1\) 次 UNION

使用路径压缩 + 按秩合并的并查集：\(O(E \cdot \alpha(V))\)

总时间 \(O(E \log E) = O(E \log V)\)（因为 \(|E| \leq |V|^2\)，\(\log |E| = O(\log V)\)）

---

Prim 算法 (CLRS 23.2)

从任意起始顶点开始，不断将连接已有树与外部顶点的最小权边加入

类似 Dijkstra 的最短路径算法，但 key 表示的是连接到树的最小边权，而非距离

算法

MST-PRIM(G, w, r):
    for each u ∈ V:
        key[u] ← ∞
        π[u] ← NIL
    key[r] ← 0
    Q ← V                          // 最小优先队列
    while Q ≠ ∅:
        u ← EXTRACT-MIN(Q)
        for each v ∈ Adj[u]:
            if v ∈ Q and w(u,v) < key[v]:
                π[v] ← u
                key[v] ← w(u,v)    // DECREASE-KEY
    return {(v, π[v]) : v ∈ V \ {r}}

不变量：

1. \(A = \{(v, \pi[v]) : v \in V \setminus Q \setminus \{r\}\}\)
2. \(Q\) 中的顶点不在 MST 子树中
3. \(\text{key}[v] = \min\{w(v, u) : u \in V \setminus Q, (v, u) \in E\}\)，即 \(v\) 连接到当前树的最小权边

正确性

点击查看证明

需证每次 EXTRACT-MIN 取出的边 \((u, \pi[u])\) 对 \(A\) 安全

设 \(S = V \setminus Q\)（已加入树的顶点）。取割 \((S, Q)\)

\(A\) 中所有边两端点都在 \(S\) 中，割尊重 \(A\)

EXTRACT-MIN 取出 \(Q\) 中 key 最小的 \(u\)。\(\text{key}[u] = w(u, \pi[u])\) 是从 \(Q\) 到 \(S\) 的最小权边

即 \((u, \pi[u])\) 是跨越割 \((S, Q)\) 的轻边

由安全边定理（定理 23.1），\((u, \pi[u])\) 对 \(A\) 安全

详细示例

时间复杂度

\[\text{时间} = |V| \cdot T(\text{Extract-Min}) + |E| \cdot T(\text{Decrease-Key})\]

优先队列	Extract-Min	Decrease-Key	总时间
数组	\(O(V)\)	\(O(1)\)	\(O(V^2)\)
二叉堆	\(O(\log V)\)	\(O(\log V)\)	\(O(E \log V)\)
斐波那契堆	\(O(\log V)\) 摊还	\(O(1)\) 摊还	\(O(E + V \log V)\)

稠密图（\(E = \Theta(V^2)\)）用数组 \(O(V^2)\) 最优

稀疏图用斐波那契堆 \(O(E + V\log V)\) 理论最优

Prim vs Kruskal

特征	Prim	Kruskal
策略	从一个顶点扩展树	选最小边连接两棵树
数据结构	优先队列	并查集
稠密图	\(O(V^2)\) 或 \(O(E + V\log V)\)	\(O(E \log E)\)
稀疏图	\(O(E \log V)\)	\(O(E \log V)\)
适用场景	稠密图更优	稀疏图或边已排序

---

并查集 (Disjoint Sets, CLRS Chapter 21)

维护不相交集合的集合 \(\{S_1, S_2, \ldots, S_k\}\)，每个集合有一个代表 (representative) 元素

操作

• \(\text{MAKE-SET}(x)\)：创建只含 \(x\) 的新集合，\(x\) 为代表
• \(\text{FIND-SET}(x)\)：返回包含 \(x\) 的集合的代表
• \(\text{UNION}(x, y)\)：合并包含 \(x\) 和包含 \(y\) 的集合

\(n\) 次 MAKE-SET 后，最多 \(n - 1\) 次 UNION（每次减少一个集合）

链表实现 (CLRS 21.2)

每个集合用链表表示，第一个元素为代表

每个节点包含：元素值、指向集合对象的指针、下一个节点指针

集合对象包含：头指针、尾指针

操作	时间
MAKE-SET	\(O(1)\)
FIND-SET	\(O(1)\)
UNION	\(O(n)\)（需更新短表每个节点的集合指针）

加权合并启发式 (weighted-union heuristic)：总是将较短链表拼接到较长链表

定理 (CLRS Theorem 21.1)：使用加权合并，\(m\) 次 MAKE-SET、UNION、FIND-SET 操作（其中 \(n\) 次 MAKE-SET）的总时间为 \(O(m + n \log n)\)

点击查看证明

FIND-SET 和 MAKE-SET 各 \(O(1)\)，共 \(O(m)\)

关键是分析所有 UNION 操作更新集合指针的总次数

考虑任意元素 \(x\)：每次 \(x\) 的集合指针被更新时，\(x\) 所在集合是较短的那个，合并后 \(x\) 所在集合的大小至少翻倍

\(x\) 所在集合从大小 1 开始，最多到大小 \(n\)

因此 \(x\) 的集合指针最多被更新 \(\lfloor \log_2 n \rfloor\) 次

\(n\) 个元素，每个最多 \(\log n\) 次更新

所有 UNION 操作的总指针更新次数 \(\leq n \log n\)

总时间 \(O(m + n \log n)\)

有根树（Up-tree）实现 (CLRS 21.3)

每个集合用一棵有根树表示，根为代表

每个节点有指向父节点的指针，根的父节点指向自己

MAKE-SET(x):
    parent[x] ← x
    rank[x] ← 0

FIND-SET(x):
    if x ≠ parent[x]:
        return FIND-SET(parent[x])
    return x

UNION(x, y):
    LINK(FIND-SET(x), FIND-SET(y))

LINK(x, y):
    parent[x] ← y

问题：不加优化的 UNION 可能导致退化为链，FIND-SET 需要 \(O(n)\)

---

按秩合并 (CLRS 21.3)

每个节点维护 \(\text{rank}\)（树高的上界）

总是将较矮的树（秩更小）挂到较高的树下

UNION-BY-RANK:
LINK(x, y):
    if rank[x] > rank[y]:
        parent[y] ← x
    else:
        parent[x] ← y
        if rank[x] = rank[y]:
            rank[y] ← rank[y] + 1

秩的性质

引理 1 (CLRS Lemma 21.2)：对任意节点 \(x\)，\(\text{rank}[x] \leq \lfloor \log_2 n \rfloor\)

点击查看证明

引理 A：秩为 \(k\) 的节点的子树至少有 \(2^k\) 个节点

归纳证明：

基础：\(k = 0\)，子树至少 \(2^0 = 1\) 个节点（自身）

归纳：秩为 \(k\) 的节点由两个秩为 \(k-1\) 的子树合并产生（秩相等时秩才增加）。每个子树至少 \(2^{k-1}\) 个节点，合并后至少 \(2^{k-1} + 2^{k-1} = 2^k\) 个节点

更严格地：秩增加到 \(k\) 只在 \(\text{rank}[x] = \text{rank}[y] = k-1\) 时发生。此时两棵子树各有 \(\geq 2^{k-1}\) 个节点，合并后 \(\geq 2^k\)

若 \(\text{rank}[x] < \text{rank}[y]\)，\(y\) 的秩不变，子树增大但秩不变，引理 A 的不等式更强

由 \(2^{\text{rank}[x]} \leq n\)，得 \(\text{rank}[x] \leq \lfloor \log_2 n \rfloor\)

引理 2 (CLRS Lemma 21.3)：秩为 \(k\) 的节点最多 \(n / 2^k\) 个

点击查看证明

每个秩为 \(k\) 的节点”统治”至少 \(2^k\) 个节点（其子树），不同的秩为 \(k\) 的节点统治的子树不相交（每个节点只有一个根祖先）

因此秩为 \(k\) 的节点数 \(\leq n / 2^k\)

推论：仅使用按秩合并（不用路径压缩），FIND-SET 和 UNION 都是 \(O(\log n)\)

---

路径压缩 (CLRS 21.3)

FIND-SET 时将路径上所有节点直接指向根

FIND-SET(x):
    if x ≠ parent[x]:
        parent[x] ← FIND-SET(parent[x])
    return parent[x]

路径压缩不改变 rank（rank 变成树高的上界而非精确值）

效果：单次 FIND-SET 做额外工作，但大幅加速后续 FIND-SET

单独使用路径压缩（不用按秩合并）：\(m\) 次操作的最坏情况 \(\Theta(m \log n)\)

路径压缩的变体

策略	描述	结合按秩合并的复杂度
完全压缩	所有节点直指根	\(O(m \cdot \alpha(n))\)
路径分裂 (path splitting)	每个节点指向祖父	\(O(m \cdot \alpha(n))\)
路径减半 (path halving)	每隔一个节点指向祖父	\(O(m \cdot \alpha(n))\)

三种策略渐近等价，但路径分裂和减半只需一趟（非递归），实践中更受欢迎

FIND-SET-SPLITTING(x):
    while x ≠ parent[x]:
        next ← parent[x]
        parent[x] ← parent[parent[x]]
        x ← next
    return x

---

按秩合并 + 路径压缩的分析

Tarjan 界

定理 (Tarjan, 1975; CLRS Theorem 21.14)：在按秩合并 + 路径压缩下，\(m\) 次 MAKE-SET、UNION、FIND-SET 操作（\(n\) 次 MAKE-SET）的总时间为 \(O(m \cdot \alpha(n))\)

\(\alpha(n)\) 是 Ackermann 函数的反函数，增长极其缓慢

\(n\)	\(\alpha(n)\)
\(1\)	\(0\)
\(2\)	\(1\)
\(4\)	\(2\)
\(16\)	\(3\)
\(65536\)	\(4\)
\(2^{65536}\)	\(5\)

对所有实际可能的 \(n\)（宇宙中原子数约 \(10^{80} \ll 2^{65536}\)），\(\alpha(n) \leq 4\)

因此按秩合并 + 路径压缩的并查集几乎是 \(O(m)\) 的

Ackermann 函数与 \(\alpha(n)\) (CLRS 21.4)

Ackermann 函数 \(A_k(j)\)（CLRS 使用的定义）：

\[A_k(j) = \begin{cases} j + 1 & k = 0 \\ A_{k-1}^{(j+1)}(j) & k \geq 1 \end{cases}\]

\(A_{k-1}^{(j+1)}(j)\) 表示将 \(A_{k-1}\) 对 \(j\) 迭代应用 \(j+1\) 次

增长极快：

• \(A_0(j) = j + 1\)
• \(A_1(j) = 2j + 1\)
• \(A_2(j) = 2^{j+1}(j + 1) - 1\)
• \(A_3(1) = A_2^{(2)}(1) = A_2(A_2(1)) = A_2(7) = 2047\)
• \(A_4(1) = A_3^{(2)}(1) = A_3(A_3(1))\)，

反 Ackermann 函数：\(\alpha(n) = \min\{k \geq 1 : A_k(1) \geq n\}\)

\(A_1(1) = 3\)，\(A_2(1) = 7\)，\(A_3(1) = 2047\)，\(A_4(1) \geq 2^{2048}\)

\(O(m \log^* n)\) 分析

更简洁但稍弱的分析给出 \(O(m \log^* n)\) 的上界（Hopcroft-Ullman 1973）

迭代对数 \(\log^* n\)：对 \(n\) 反复取 \(\log_2\) 直到 \(\leq 1\) 的次数

\(n\)	\(\log^* n\)
\(2\)	\(1\)
\(4\)	\(2\)
\(16\)	\(3\)
\(65536\)	\(4\)
\(2^{65536}\)	\(5\)

点击查看 log* 分析

势函数分析：将节点按 rank 分组

组 \(0\)：rank \(= 0\)

组 \(1\)：rank \(= 1\)

组 \(2\)：rank \(= 2\)

组 \(3\)：rank \(\in \{3, 4\}\)

组 \(4\)：rank \(\in \{5, 6, \ldots, 16\}\)

组 \(5\)：rank \(\in \{17, 18, \ldots, 65536\}\)

一般地，组 \(g\) 包含 rank \(r\) 满足 \(\log^* r = g\) 的所有节点

引理 A：不同组的数量 \(\leq \log^* n + 1\)

因为最大 rank \(\leq \lfloor \log n \rfloor\)

引理 B：令组 \(g\) 对应的 rank 范围为 \((k, 2^k]\)

该组中的节点总数 \(\leq n / 2^{k}\)

因为秩为 \(r\) 的节点最多 \(n/2^r\) 个，对组内所有 \(r\) 求和并利用几何级数

代价分析：

FIND-SET 追踪路径 \((x, \text{parent}[x])\) 时：

• 若 \(x\) 和 \(\text{parent}[x]\) 在不同组：由 FIND-SET 支付。每次 FIND-SET 路径上最多 \(\log^* n + 1\) 次跨组

• 若 \(x\) 和 \(\text{parent}[x]\) 在同组：由 \(x\) 的令牌支付

为组 \(g\)（rank 范围 \((k, 2^k]\)）中的每个节点分配 \(2^k\) 个令牌

该组的总令牌数 \(\leq 2^k \cdot n / 2^{k} = n\)（更精确的计算给出 \(\leq 2n\)）

关键观察：每次路径压缩后，\(x\) 的父节点变为根，根的 rank 高于 \(x\) 的旧父节点。在同一组内，\(x\) 最多被收费 \(2^k\) 次后，其父节点的 rank 必然超出当前组

所有组的总令牌数 \(\leq (\log^* n + 1) \cdot 2n = O(n \log^* n)\)

\(m\) 次 FIND-SET 的跨组代价 \(\leq m(\log^* n + 1)\)

总代价 \(\leq m(\log^* n + 1) + O(n \log^* n) = O((m + n) \log^* n) = O(m \log^* n)\)

（因为 \(m \geq n\)）

CLRS 的势函数分析 (CLRS 21.4)

CLRS 使用精确的势函数证明 \(O(m \cdot \alpha(n))\) 界

点击查看分析框架

定义节点 \(x\) 的级别 (level) 和迭代次数 (iter)（在 \(x\) 不是根且不是根的直接子节点时）：

\[\text{level}(x) = \max\{k : \text{rank}[\text{parent}(x)] \geq A_k(\text{rank}[x])\}\]

\[\text{iter}(x) = \max\{i : \text{rank}[\text{parent}(x)] \geq A_{\text{level}(x)}^{(i)}(\text{rank}[x])\}\]

其中 \(0 \leq \text{level}(x) \leq \alpha(n)\)，\(1 \leq \text{iter}(x) \leq \text{rank}[x]\)

势函数：

\[\Phi = \sum_{x: x \text{ 不是根}} \phi(x)\]

\[\phi(x) = \begin{cases} \alpha(n) \cdot \text{rank}[x] & x \text{ 是根或根的子节点} \\ (\alpha(n) - \text{level}(x)) \cdot \text{rank}[x] - \text{iter}(x) & \text{否则} \end{cases}\]

关键引理：

1. \(0 \leq \phi(x) \leq \alpha(n) \cdot \text{rank}[x]\)
2. FIND-SET 的摊还代价 \(\leq \alpha(n) + O(1)\)（路径压缩增加 level 或 iter，减少势能）

因此 \(m\) 次操作的总摊还代价 \(= O(m \cdot \alpha(n))\)

下界

定理 (Fredman & Saks, 1989)：在 cell-probe 模型下，\(m\) 次并查集操作（\(n\) 次 MAKE-SET）需要 \(\Omega(m \cdot \alpha(n))\) 时间

因此 Tarjan 的 \(O(m \cdot \alpha(n))\) 界是渐近最优的

并查集的应用

应用	说明
Kruskal MST	检测环 / 判断连通性
连通分量	动态维护图的连通分量
等价类合并	编译器中的类型推断
Tarjan LCA	离线最近公共祖先
渗透 (percolation)	物理系统中的连通性判断
图像处理	连通区域标记

---

Borůvka 算法

最早的 MST 算法 (Borůvka, 1926)，思想简单且易于并行化

BORŮVKA(G, w):
    T ← ∅
    while 连通分量数 > 1:
        for each 连通分量 C:
            找 C 的最小权外边 e_C
        T ← T ∪ {e_C : 对所有 C}
        收缩已连接的分量
    return T

分析

每轮至少将连通分量数减半（每个分量至少与一个其他分量合并）

最多 \(O(\log V)\) 轮，每轮 \(O(E)\)

总时间 \(O(E \log V)\)

优势

并行友好：每轮中各分量独立找最小外边，天然适合 PRAM 并行计算

Borůvka 是随机线性时间 MST 的关键组件（Karger-Klein-Tarjan 1995）

---

Red-Blue 元算法 (Tarjan)

Tarjan 在论文中提出了一个框架——Red-Blue 元算法，将 Kruskal、Prim、Borůvka 都视为特例

两条着色规则

蓝色规则 (Blue Rule)：选择任意没有蓝色边跨越的割，将跨越该割的最小权无色边染蓝

红色规则 (Red Rule)：选择任意没有红色边的环，将环上最大权无色边染红

元算法

RED-BLUE-MST(G, w):
    所有边初始为无色
    while 存在无色边:
        应用蓝色规则或红色规则
    return 蓝色边集合

定理 (Tarjan)：无论以何种顺序应用规则，算法终止时蓝色边集合恰好是 MST（边权互不相同时）

统一视角

算法	Red-Blue 视角
Kruskal	对最小无色边：若不成环 → 蓝色规则；若成环 → 红色规则
Prim	蓝色规则，割总是当前树 vs 其余
Borůvka	蓝色规则，同时对所有分量应用
反向删除	红色规则，从最大边开始

反向删除算法 (Reverse-Delete)：按边权从大到小考虑，若删除不断开图则删除

这是红色规则的直接实现，时间 \(O(E \log V \cdot \log \log V)\)（需要动态连通性数据结构）

---

随机线性时间 MST

Karger, Klein, Tarjan (1995) 提出了期望 \(O(E)\) 的随机 MST 算法

核心思想：

1. 运行 2 轮 Borůvka，将分量数降到 \(V/4\)
2. 对每条边独立地以概率 \(1/2\) 采样，递归求采样图的 MST（称为 \(F\)）
3. 用 \(F\) 过滤原图：删除不可能在 MST 中的边（\(F\)-heavy 边）
4. 递归求过滤后图的 MST

验证 \(F\)-heavy 边使用随机线性时间的路径最大值查询

期望时间 \(T(V, E) = T(V/4, E/2) + T(V/4, E/2) + O(E) = O(E)\)

---

次小生成树 (CLRS Problem 23-1)

问题

给定图 \(G\) 和 MST \(T\)，找权重第二小的生成树

\(O(V^2)\) 算法

对 MST \(T\) 中每对顶点 \((u,v)\)，预计算路径上的最大边权 \(\max[u,v]\)

\[w(T') = w(T) - \max[u,v] + w(u,v)\]

遍历所有非树边 \((u,v)\)，找使 \(w(u,v) - \max[u,v]\) 最小的

点击查看详细算法

预计算 \(\max[u,v]\)：对 MST 做 DFS，对每个节点 \(u\) 用 BFS/DFS 计算到其他所有节点的路径最大边权

时间 \(O(V^2)\)

枚举非树边：对每条 \((u,v) \notin T\)：

\[\text{swap\_cost}(u,v) = w(u,v) - \max[u,v]\]

最小正值的 swap_cost 对应次小生成树

\[w(T_{\text{second}}) = w(T) + \min_{(u,v) \notin T, w(u,v) > \max[u,v]} \text{swap\_cost}(u,v)\]

若所有边权互不相同，\(w(u,v) > \max[u,v]\) 必定成立（否则 \(T\) 不是 MST）

\(O(E \alpha(V))\) 算法（Tarjan 方法）

使用 LCA (最近公共祖先) 和路径最大值查询，将预计算降到近线性

---

MST 验证问题 (King, 1997 / MIT 6.854)

问题：给定生成树 \(T\)，验证 \(T\) 是否是 MST

定理 (King, 1997)：MST 验证可在 \(O(V + E)\) 时间内完成

算法利用 Komlós (1985) 的结论：只需对每条非树边 \((u,v)\) 检查 \(w(u,v) \geq \max_{e \in P(u,v)} w(e)\)

其中 \(P(u,v)\) 是 \(T\) 中 \(u\) 到 \(v\) 的路径

Komlós 证明只需 \(O(V + E)\) 次比较，King 给出了相应的高效实现

---

附录

MST 算法总结

算法	时间	特点
Prim (数组)	\(O(V^2)\)	稠密图最优
Prim (Fibonacci 堆)	\(O(E + V\log V)\)	理论最优之一
Kruskal	\(O(E \log V)\)	简单
Borůvka	\(O(E \log V)\)	易于并行化
Karger-Klein-Tarjan (1995)	\(O(E)\) 期望	随机线性时间
Chazelle (2000)	\(O(E \cdot \alpha(E,V))\)	确定性近线性

是否存在 \(O(E)\) 确定性 MST 算法仍是开放问题

MST 与拟阵

Kruskal 算法本质上是加权拟阵上的贪心

图拟阵 \(M_G = (E, \mathcal{I})\)：\(\mathcal{I}\) 中的独立集是 \(G\) 的森林（无环边集）

Kruskal 按权重递增贪心选边，是加权拟阵贪心算法的例子

取最小权（将权重取负后求最大权独立集），Kruskal 产生 MST

瓶颈生成树

瓶颈生成树 (Bottleneck Spanning Tree)：最小化生成树中最大边权

定理：MST 也是瓶颈生成树

点击查看证明

设 \(T\) 是 MST，\(T^*\) 是瓶颈生成树。设 \(e^* = \max_{e \in T^*} w(e)\)

若 \(T\) 不是瓶颈生成树，则存在边 \(e \in T\)，\(w(e) > e^*\)

移除 \(e\) 将 \(T\) 分为 \(T_1\) 和 \(T_2\)

\(T^*\) 连通，必有边 \(e'\) 跨越 \((T_1, T_2)\)，\(w(e') \leq e^* < w(e)\)

\(T' = T \setminus \{e\} \cup \{e'\}\) 是生成树，\(w(T') < w(T)\)，矛盾

反之不然：瓶颈生成树不一定是 MST

单链接聚类

给定 \(n\) 个数据点和距离函数 \(d\)，将数据分为 \(k\) 个簇，最大化簇间距离（不同簇中最近两点的距离）

算法：运行 Kruskal 算法，在加入第 \(n - k\) 条边后停止

此时恰好有 \(k\) 个连通分量，即 \(k\) 个簇

点击查看正确性

定理：Kruskal 聚类最大化了簇间最小距离

设 Kruskal 停止时的 \(k\) 个簇为 \(C_1, \ldots, C_k\)，簇间距离为 \(d^*\)（即第 \(n-k+1\) 条边的权重）

考虑任意其他 \(k\)-聚类 \(C'_1, \ldots, C'_k\)

由鸽巢原理，存在某个 \(C_r\) 被分到了两个不同的 \(C'\) 簇中

\(C_r\) 中连接这两个 \(C'\) 簇的路径上，必有一条边跨越 \(C'\) 的簇边界

该边权重 \(\leq d^*\)（因为 \(C_r\) 中的边都在前 \(n-k\) 条中选出）

因此 \(C'\) 的簇间距离 \(\leq d^*\)