• Minimum Spanning Trees

• Prim’s Algorithm

  • Prim’s Demo (Conceptual)
  • Realistic Implementation Demo

• Kruskal’s Algorithm

  • Kruskal’s Conceptual Demo
  • Kruskals Optimized Implementation Demo

最小生成树 (Minimum Spanning Trees, MST)

一、 图算法预热问题：无向图的环判定 (Cycle Detection)

【问题定义】：给定一个无向图 $G = (V, E)$，如何判断该图中是否存在环？

方法 1：基于深度优先搜索 (DFS)

• 核心思想： 从任意未访问的顶点开始进行 DFS。在搜索过程中，如果遇到一个已被标记（marked）的邻接顶点，说明存在环。
• 潜在陷阱与解决方案：
  • 陷阱：无向图中的边是双向的。当从顶点 $A$ 访问到 $B$ 时，$B$ 的邻居中必然包含 $A$。如果直接检查已标记的邻居，会误将“走回头路（回到父节点）”判定为环。
  • 解决方案：在 DFS 递归调用中传入当前节点的父节点（即来源节点），不将父节点视为成环的标记点。
• 时间复杂度：
  • 最坏情况：$O(V + E)$。
  • 优化分析：对于无向图，一旦检查的边数超过 $V-1$，根据树的性质，图中必然已经包含环。因此，我们可以限制检查的边数，从而将最坏情况时间复杂度收紧为 $O(V)$。

方法 2：基于加权并查集 (Weighted Quick Union with Path Compression, WQUPC)

• 核心思想： 遍历图中的每一条边 $v-w$：
  1. 调用 connected(v, w) 检查 $v$ 和 $w$ 是否已经连通。
  2. 如果 不连通，说明当前边不会构成环，调用 union(v, w) 将它们合并到同一个连通分量中。
  3. 如果 已连通，说明在添加这条边之前， $v$ 和 $w$ 之间就已经存在一条通路，现在加上这条边必然会构成一个环，直接返回 true（存在环）。
• 时间复杂度：
  • 最坏情况：包含路径压缩时，每次 Union-Find 操作耗时为 $O(\alpha(V))$（其中 $\alpha$ 是反阿克曼函数，增长极其缓慢，在实际中可视为常数）。
  • 遍历所有边：$O(V + E\alpha(V))$。同样，因为一旦加入第 $V$ 条边必然成环，所以实际最多进行 $V$ 次 union 操作，总时间复杂度可以简化为 $O(V\alpha(V))$。

二、 最小生成树 (MST) 的概念与割性质 (Cut Property)

1. 生成树 (Spanning Tree) 的定义

给定一个无向连通图 $G = (V, E)$，其生成树 $T$ 是 $G$ 的一个子图，且必须满足以下三个条件：

1. 连通性：包含图中的所有顶点。
2. 无环性（Acyclic）：不包含任何环。
3. 顶点全覆盖：包含全部 $V$ 个顶点，且只有 $V-1$ 条边。

最小生成树 (MST)：在所有可能的生成树中，边权值之和最小的生成树。 注：若图中的边权值均不相同，则该图的 MST 是唯一的。为了讨论简便，后续均默认边权值唯一。

2. 割性质 (Cut Property) — 寻找 MST 的基石

• 割 (Cut)：将图中的顶点划分为两个非空、互不相交的集合（例如灰色顶点集合与白色顶点集合）。
• 横跨边 (Crossing Edge)：一条端点分别属于这两个不同集合的边。

$\text{\textbf{割性质定理}：给定任意一种割方式，所有横跨边中权值最小的那条边必然属于该图的 MST。}$

割性质的数学证明（反证法）

1. 假设 $T$ 是图 $G$ 的 MST，但权值最小的横跨边 $e$ 不在 $T$ 中。
2. 如果我们将 $e$ 添加到 $T$ 中，由于 $T$ 是生成树，加入一条边必然会形成一个唯一的环。
3. 这个环中必定存在另外一条横跨该割的边 $f$（因为环要跨过去再跨回来才能闭合）。
4. 显然，边 $f$ 的权值 $w(f) > w(e)$（因为 $e$ 是所有横跨边中权值最小的）。
5. 如果我们用 $e$ 替换 $f$（即令 $T' = T \cup \{e\} \setminus \{f\}$），得到的 $T'$ 仍然是一棵连通且无环的生成树，但其总权重 $W(T') = W(T) + w(e) - w(f) < W(T)$。
6. 这与 $T$ 是 最小 生成树的假设产生矛盾！因此，最小横跨边 $e$ 必须包含在 MST 中。

💡 割性质应用例题

【题目】：已知割集合为 $\{2, 3, 5, 6\}$（如下图中的紫色顶点），剩余顶点 $\{0, 1, 4, 7\}$ 为另一侧。给定以下边权值列表，请找出哪条边属于该割的最小权重横跨边（必在 MST 中）？

【解析过程】：

1. 首先，识别出所有一端在 $\{2, 3, 5, 6\}$，另一端在 $\{0, 1, 4, 7\}$ 的 横跨边：

   • $2$ 的外部邻居：$0-2$ (0.26), $2-7$ (0.34), $1-2$ (0.36)
   • $3$ 的外部邻居：$1-3$ (0.29)
   • $5$ 的外部邻居：$5-7$ (0.28), $1-5$ (0.32), $4-5$ (0.35)
   • $6$ 的外部邻居：$6-0$ (0.58), $6-4$ (0.93) (注：像 2-3、3-6 这样两端都在同一颜色集合内部的边不是横跨边)

2. 在所有找到的横跨边中，比较它们的权值：

   $\text{横跨边集合：} \{0-2(0.26), 2-7(0.34), 1-2(0.36), 1-3(0.29), 5-7(0.28), 1-5(0.32), 4-5(0.35), 6-0(0.58), 6-4(0.93)\}$

3. 其中权值最小的是边 $0-2$ (权值为 0.26)。

4. 【结论】：根据割性质，边 $0-2$ 必定在 MST 中。

3. 通用 MST 寻找算法 (SOP)

基于割性质，我们可以设计出寻找 MST 的通用框架：

1. 起初，MST 的边集为空。
2. 寻找一个割，使得该割的所有横跨边中，目前没有一条已经被选入 MST。
3. 找到该割中 权重最小的横跨边，将其加入 MST 边集。
4. 重复上述步骤，直到 MST 中包含了 $V-1$ 条边。

三、 Prim 算法（普里姆算法）

1. 概念化设计 (Conceptual / Ideal)

• 思想：从一个任意的起始顶点 $s$ 开始，将其放入已经构建的树中。在每一步中，寻找有一个端点在树内，另一个端点在树外的所有边（即以“当前树的顶点集合”和“其余顶点集合”作为割），选择其中权重最小的边，将树外的那个邻接点及该边并入树中。
• 终止条件：重复此步骤，直到树中包含了所有 $V$ 个顶点（即合入了 $V-1$ 条边）。

2. 高效实现设计 (Realistic / Optimized)

如果每次都去遍历所有横跨边，效率会非常低下（如你手写笔记所说：“Iterating over all magenta edges is unnecessary and slow”）。

• 解决方案：引入优先队列 (PQ, Fringe)。
  • 队列中的元素为：顶点 $v$ 以及当前已知的 $v$ 到正在构建的 MST 的最短距离 (distTo[v])。
  • 每次从优先队列中取出 distTo 最小的顶点 $v$（即离当前 MST 最近的未访问点）。
  • 接着，进行松弛操作 (Relaxation)：遍历 $v$ 的所有邻接边 $v-w$，如果发现边 $v-w$ 的权重比 $w$ 当前记录的 distTo[w] 还要小，则更新 distTo[w] = e.weight() 并将 edgeTo[w] = e，同时降低其在 PQ 中的优先级。

🌟 经典对比：Prim vs. Dijkstra

维度	Dijkstra 算法	Prim 算法
关注核心	寻找单源最短路径树 (SPT)	寻找最小生成树 (MST)
访问顺序	顶点按照到源点 $s$ 的总路径累加距离从小到大被访问	顶点按照到当前 MST 整体的最近距离从小到大被访问
松弛机制 (Relaxation)	distTo[w] > distTo[v] + e.weight()	distTo[w] > e.weight()
边权值要求	不能处理含有负权值的图（会失效）	可以正确处理含有负权值的图（只要无负环）

❓ 思考题：MST 也是某一顶点的 SPT 吗？

【问题】：对于一个给定的图，其 MST 是否也必然是某一个特定起点下的 SPT？ 【解答】：不一定。 如下图所示：

      B  —— 1 ——  C
    /              \
   2                2
  /                  \
A —— 2 —— D —— 2 —— s

其 MST 必须选择权重最小的边。如果我们选择底部左侧的起点，在生成 SPT 时为了使到各点的绝对距离最短，会引入更多的 2 权重边，而 MST 只会保留必需的 $V-1$ 条边。因此，SPT 严重依赖于起点的选择，而 MST 关注的是整体连接成本的最优化，两者并不等价。

3. 代码实现 (Java) $\bigstar$

根据课件和手写笔记要求，以下为 Prim 算法的完整 Java 实现：

import java.util.ArrayList;
import java.util.List;

public class PrimMST {
    private Edge[] edgeTo;       // edgeTo[v] = 离当前 MST 最近的边
    private double[] distTo;     // distTo[v] = 顶点 v 到当前 MST 的最小距离
    private boolean[] marked;    // marked[v] = true 表示 v 已经在 MST 中
    private IndexMinPQ<Double> pq; // 索引优先队列，用于动态获取最近的顶点

    public PrimMST(EdgeWeightedGraph G) {
        edgeTo = new Edge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        pq = new IndexMinPQ<Double>(G.V());

        // 初始化所有顶点的距离为无穷大
        for (int v = 0; v < G.V(); v++) {
            distTo[v] = Double.POSITIVE_INFINITY;
        }

        // 从顶点 0 开始构建 MST
        distTo[0] = 0.0;
        pq.insert(0, 0.0);
        
        while (!pq.isEmpty()) {
            int v = pq.delMin(); // 取出离 MST 最近的顶点
            scan(G, v);
        }
    }

    // 松弛与该顶点相连的所有边
    private void scan(EdgeWeightedGraph G, int v) {
        marked[v] = true; // 将该顶点正式合入 MST
        for (Edge e : G.adj(v)) {
            int w = e.other(v);
            if (marked[w]) continue; // 邻接点已在 MST 中，跳过（防止成环）
            
            if (e.weight() < distTo[w]) {
                distTo[w] = e.weight(); // 更新 w 到当前树的最近距离
                edgeTo[w] = e;
                if (pq.contains(w)) {
                    pq.decreaseKey(w, distTo[w]); // 降低优先级
                } else {
                    pq.insert(w, distTo[w]);
                }
            }
        }
    }

    // 获取 MST 中的所有边
    public Iterable<Edge> edges() {
        List<Edge> mst = new ArrayList<>();
        for (int v = 0; v < edgeTo.length; v++) {
            if (edgeTo[v] != null) {
                mst.add(edgeTo[v]);
            }
        }
        return mst;
    }
}

4. Prim 算法时间复杂度推导

为什么使用二叉堆（Binary Heap）实现优先队列时，Prim 算法的运行时间是 $O(E \log V)$？

我们将 Prim 算法的每个操作拆解分析：

操作步骤	执行次数	单次时间复杂度	总时间开销
PQ 插入顶点 (insert)	$V$	$O(\log V)$	$O(V \log V)$
取出最小顶点 (delMin)	$V$	$O(\log V)$	$O(V \log V)$
降低优先级 (decreaseKey)	最坏情况 $E$	$O(\log V)$	$O(E \log V)$

• 总开销之和：

  $T(V, E) = O(V \log V + V \log V + E \log V)$

• 简化分析： 在连通图（Connected Graph）中，边的数量一定满足 $E \ge V - 1$。因此 $E \log V \ge V \log V$。 由此可得，总时间复杂度由最大的项决定，即：

  $O(E \log V)$

四、 Kruskal 算法（克鲁斯卡尔算法）

1. 概念化设计 (Conceptual / Ideal)

• 核心思想： 不要限制在“从单个顶点开始向外延展”。我们将图中的所有边看作一个整体：
  1. 将图中的所有边按照权值从小到大进行排序。
  2. 依次选择当前权值最小的边。
  3. 检查：加入这条边是否会在已选的 MST 边集中构成环？
     • 若 不会构环：正式将该边加入 MST。
     • 若 会构环：舍弃该边。
  4. 重复此操作，直到选出了 $V-1$ 条边。

2. 优化实现设计：如何解决“每次判断是否有环开销太大”的问题？

💡 纠正手写笔记中的疑惑： > 你在笔记中写道：“每次都判断是否有环，开销是不是太大了？” 解答：如果使用常规的 DFS 查找环，每次查环的开销为 $O(V)$，对于所有边总开销会飙升至 $O(E \cdot V)$，开销确实极其庞大。 为了彻底解决这个性能瓶颈，我们引入了**并查集（Union-Find）**数据结构！

• 并查集是如何工作的？
  • 在并查集中，初始时每个顶点都是一个独立的连通分量（集合）。
  • 当我们要考虑一条边 $v-w$ 时：
    • 仅需要调用 uf.connected(v, w) 来查询 $v$ 和 $w$ 是否处于同一个连通分量中。
    • 如果不在同一个集合中，说明此时加入这条边绝对不会产生环，紧接着调用 uf.union(v, w) 将两者的集合合并。
    • 如果已经在同一个集合中，说明加入此边会产生环，直接抛弃。
  • 利用带有路径压缩和按秩合并的加权并查集，connected 和 union 操作的单次时间复杂度仅为几乎常数的 $O(\log^\* V)$。这使得成环检测几乎“免费”，彻底解决了性能瓶颈！

3. 代码实现 (Java) $\bigstar$

根据手写笔记要求，Kruskal 算法的经典实现如下：

import java.util.ArrayList;
import java.util.List;

public class KruskalMST {
    private List<Edge> mst = new ArrayList<Edge>(); // 存储最终 MST 的边集

    public KruskalMST(EdgeWeightedGraph G) {
        // 1. 将所有边插入一个最小优先队列中以实现自动排序
        MinPQ<Edge> pq = new MinPQ<Edge>();
        for (Edge e : G.edges()) {
            pq.insert(e);
        }

        // 2. 初始化并查集，初始时每个顶点都是独立集合
        WeightedQuickUnionPC uf = new WeightedQuickUnionPC(G.V());

        // 3. 循环获取最小边，直到队列为空或已选够 V-1 条边
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.delMin(); // 取出权值最小的边
            int v = e.from();
            int w = e.to();

            // 利用并查集判断 v 和 w 是否已连通（即加入该边是否会成环）
            if (!uf.connected(v, w)) { 
                uf.union(v, w); // 合并两个不相交集合
                mst.add(e);     // 将该边安全加入 MST
            }
        }
    }

    public Iterable<Edge> edges() {
        return mst;
    }
}

4. 彻底攻克：Kruskal 算法的 Runtime 计算与推导

为了让你完全看懂 Kruskal 的时间复杂度计算，我们将所有核心操作和其调用次数进行逐步拆解。

场景 A：使用最小优先队列（Min-PQ）的一般情况

假设图中有 $V$ 个顶点，$E$ 条边，我们采用二叉堆（Binary Heap）实现 Min-PQ。

操作步骤	调用次数	单次时间复杂度	总时间复杂度
将所有边插入 PQ (insert)	$E$ 次	$O(\log E)$	$O(E \log E)$
取出最小边 (delMin)	最坏 $E$ 次	$O(\log E)$	$O(E \log E)$
并查集连通判断 (connected)	最坏 $E$ 次	$O(\log^* V)$	$O(E \log^* V)$
并查集合并 (union)	恰好 $V-1$ 次	$O(\log^* V)$	$O(V \log^* V)$

• 整体累加复杂度：

  $T(V, E) = O(E \log E + E \log E + E \log^* V + V \log^* V)$

  因为 $E \log E$ 的增长速度远快于具有反阿克曼尺度的 $E \log^* V$，所以总复杂度由 PQ 的操作占主导，即：

  $\mathbf{O(E \log E)}$

• 🎉 关键数学转换：为什么 $O(E \log E) = O(E \log V)$？ 由于图中任意两点间最多只有一条边，所以最大边数限制为 $E \le V^2$。 我们将 $E \le V^2$ 带入 $\log E$ 中进行缩放：

  $\log E \le \log(V^2) = 2 \log V$

  根据大 $O$ 表示法的常数忽略性质，$\log E$ 在渐进意义上等价于 $\log V$。因此：

  $\mathbf{O(E \log E) \equiv O(E \log V)}$

  (这说明在最坏情况下，Kruskal 算法和 Prim 算法在渐进时间复杂度上是完全一致的。)

场景 B：高级优化技巧（Heapification 与预排序）

1. 利用“自底向上堆化（Bottom-up Heapification）”优化 PQ 初始化

• 原理解析：在 HeapSort 中我们会学到，若将一个无序的包含 $E$ 个元素的数组构建成堆，如果逐个调用 insert，开销是 $O(E \log E)$。但如果直接使用“下沉松弛（Sink-based heapify）”，可以将建堆的时间大幅缩短至 $O(E)$。
• 对整体复杂度的影响：虽然初始化变快成了 $O(E)$，但我们后续仍需进行最多 $E$ 次 delMin 操作（每次开销 $O(\log E)$），因此总复杂度依然为 $O(E \log E)$。

2. 预排序边集（Pre-sorted Edges）的最极致优化情况

• 原理解析：如果图中的边在输入时就已经排好序，或者我们可以使用基数排序（Radix Sort，在某些特定整数边权下可用）在 $O(E)$ 时间内排好序：

  • 我们将不再需要 PQ，而是直接使用普通循环遍历已排好序的数组（每次取最小边只需 $O(1)$ 的时间，共进行 $E$ 次，总共 $O(E)$）。
  • 此时，算法的所有耗时将彻底由 Union-Find 统治！

• 此时的总复杂度推导：

  $T(V, E) = \underbrace{O(E)}_{\text{遍历已排好序的边}} + \underbrace{O(E \log^* V)}_{\text{并查集成环检测}} = \mathbf{O(E \log^* V)}$

  由于 $\log^* V$ 在宇宙范围内其值都不超过 5，所以此时的 Kruskal 算法可以说是达到了惊人的近乎线性时间复杂度！

五、 最短路径与 MST 算法终极对比表

算法	解决问题类型	时间复杂度 (若 $E > V$)	适用条件与备注说明
Dijkstra 算法	单源最短路径树 (SPT)	$O(E \log V)$	不能处理存在负权重边的图。
Prim 算法	最小生成树 (MST)	$O(E \log V)$	适合稠密图，逻辑与 Dijkstra 几乎完全一致。
Kruskal 算法	最小生成树 (MST)	$O(E \log E) = O(E \log V)$	适合稀疏图，利用 WQUPC 实现极其高效的成环检测。
Kruskal 算法 (预排序边)	最小生成树 (MST)	$O(E \log^* V)$	极速版。适用于边权已排序或可线性时间排序的场景。

---

CLRS 第 21 章：最小生成树 (MST) 深度巩固练习指南

本指南紧扣你上传的《算法导论》第 21 章教材，挑选了最经典的课后习题与思考题。这些题目将帮助你深入理解割性质 (Cut Property)、环性质 (Cycle Property) 以及 Prim/Kruskal 算法的边界条件。

目录

1. 第一阶段：割性质与 MST 基本理论 (21.1 节)
2. 第二阶段：Kruskal 与 Prim 算法执行细节 (21.2 节)
3. 第三阶段：经典高阶思考题 (次小生成树)

第一阶段：割性质与 MST 基本理论 (21.1 节)

这一节的习题旨在帮你巩固割性质的证明逻辑，并引入另一个极度对称的重要性质——环性质 (Cycle Property)。

✍️ 练习 21.1-1 (经典结论证明)

• 英文原题：

  Let $G = (V, E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S, V-S)$ be any cut of $G$ that respects $A$, and let $(u, v)$ be a light edge crossing $(S, V-S)$. Show that $(u, v)$ is safe for $A$.

• 中文翻译： 设 $G = (V, E)$ 为一个带权无向连通图。设 $A$ 是 $E$ 的一个子集，且 $A$ 包含在 $G$ 的某棵最小生成树中。设 $(S, V-S)$ 是 $G$ 的任意一个不破坏 $A$（即 $A$ 中没有边横跨该割）的割，且 $(u, v)$ 是横跨该割的一条轻边（即权重最小的横跨边）。证明：边 $(u, v)$ 对于集合 $A$ 是安全的（即 $A \cup \{(u, v)\}$ 依然包含在某棵 MST 中）。

• 核心考点： 割性质定理的严格证明（反证法与替换法）。

• 解题思路提示 (Hint)：

  1. 设 $T$ 是包含 $A$ 的一棵 MST。如果 $(u, v) \in T$，则结论显然成立。
  2. 如果 $(u, v) \notin T$，那么将 $(u, v)$ 加入 $T$ 会形成一个包含 $(u, v)$ 的唯一环。
  3. 因为 $u \in S$ 且 $v \in V-S$，这个环中必然存在另一条横跨 $(S, V-S)$ 的边 $(x, y)$。
  4. 考虑构造一棵新树 $T' = T - \{(x, y)\} \cup \{(u, v)\}$，证明 $w(T') \le w(T)$，从而得出 $T'$ 也是 MST 的结论。

【证明步骤】：

1. 假设包含 $A$ 的 MST 为 $T$。若 $(u, v) \in T$，则 $A \cup \{(u, v)\} \subseteq T$，边 $(u, v)$ 显然安全。

2. 若 $(u, v) \notin T$，由于 $T$ 是生成树，我们将 $(u, v)$ 加入 $T$ 中，在 $T \cup \{(u, v)\}$ 中必然包含一个唯一的环 $C$。

3. 由于 $u \in S$ 且 $v \in V-S$，环 $C$ 必须跨越割 $(S, V-S)$ 至少两次才能闭合。因此，在环 $C$ 上必然存在另一条横跨该割的边 $(x, y) \neq (u, v)$。

4. 因为割 $(S, V-S)$ 尊重 $A$，所以横跨边 $(x, y)$ 绝对不属于 $A$（因为 $A$ 中没有横跨边）。因此 $A \subseteq T - \{(x, y)\}$。

5. 因为 $(u, v)$ 是横跨割 $(S, V-S)$ 的轻边（最小权重边），所以有：

   $w(u, v) \le w(x, y)$

6. 我们构造一棵新树 $T' = T - \{(x, y)\} \cup \{(u, v)\}$。

   • 连通性与无环性：由于我们从环中删去了一条边 $(x, y)$ 并加入了一条同样能连接两个分量的边 $(u, v)$，$T'$ 依然是一棵合法的生成树。

   • 权重对比：

     $w(T') = w(T) - w(x, y) + w(u, v)$

     因为 $w(u, v) \le w(x, y)$，所以有 $w(T') \le w(T)$。

7. 又因为 $T$ 已经是 MST（权重最小），所以 $w(T')$ 只能等于 $w(T)$。这意味着 $T'$ 也是一棵 MST。

8. 显然，$A \cup \{(u, v)\} \subseteq T'$。因此，$(u, v)$ 对于 $A$ 是安全的。$\blacksquare$

✍️ 练习 21.1-5 (环性质 Cycle Property)

• 英文原题：

  Let $e$ be a maximum-weight edge on some cycle $C$ in $G = (V, E)$. Prove that there is a minimum spanning tree of $G' = (V, E - \{e\})$ that is also a minimum spanning tree of $G$. That is, there exists a minimum spanning tree of $G$ that does not include $e$.

• 中文翻译： 设 $e$ 是图 $G = (V, E)$ 中某个环 $C$ 上权重最大的边。证明：图 $G' = (V, E - \{e\})$ 的最小生成树同时也是 $G$ 的最小生成树。换句话说，存在一棵不包含边 $e$ 的图 $G$ 的最小生成树。

• 核心考点： 环性质 (Cycle Property)。这是与割性质齐名的图性质：在任意一个环中，权重严格最大的边一定不在 MST 中。

• 解题思路提示 (Hint)：

  1. 设 $T$ 是 $G$ 的任意一棵包含 $e$ 的 MST。
  2. 如果我们把 $e$ 从 $T$ 中删去，$T$ 会分裂成两个不连通的连通分量 $T_1$ 和 $T_2$。
  3. 因为 $e$ 原本处于环 $C$ 上，环上的其他边必然可以提供另一条通路连接 $T_1$ 和 $T_2$。
  4. 找到环 $C$ 上除 $e$ 之外的另一条横跨 $T_1$ 和 $T_2$ 的边 $e'$，比较 $w(e)$ 和 $w(e')$。

【证明步骤】：

1. 假设 $T$ 是 $G$ 的一棵包含边 $e$ 的 MST。若能证明存在另一棵权重相同的 MST 不包含 $e$，则命题成立。

2. 从 $T$ 中移除边 $e$。此时 $T$ 被分割为两棵不相交的子树 $T_1$ 与 $T_2$。这在顶点集上隐式地定义了一个割 $(V_1, V_2)$，其中 $T_1$ 覆盖 $V_1$，$T_2$ 覆盖 $V_2$。

3. 边 $e$ 是横跨割 $(V_1, V_2)$ 的一条边。

4. 既然 $e$ 属于环 $C$，如果我们沿着环 $C$ 从 $e$ 的一个端点出发走到另一个端点，路径上必然存在另一条边 $e'$ 横跨割 $(V_1, V_2)$（因为环必须从 $V_1$ 跨到 $V_2$ 再跨回来）。

5. 题目指出 $e$ 是环 $C$ 上权重最大的边，所以必有：

   $w(e') \le w(e)$

6. 我们构造新图 $T' = T - \{e\} \cup \{e'\}$：

   • $T'$ 连接了所有的顶点且无环，是一棵生成树。

   • 它的总权重为：

     $w(T') = w(T) - w(e) + w(e')$

   • 因为 $w(e') \le w(e)$，所以 $w(T') \le w(T)$。

7. 因为 $T$ 已经是 MST，所以必有 $w(T') = w(T)$。因此 $T'$ 也是 $G$ 的一棵最小生成树。

8. 由于 $T'$ 不包含边 $e$，它同时也是移除了边 $e$ 之后的子图 $G'$ 的一棵 MST。$\blacksquare$

✍️ 练习 21.1-8 (权值单调递增变换)

• 英文原题：

  Let $T$ be a minimum spanning tree of a graph $G = (V, E)$, and let $V'$ be a subset of $V$. Let $T'$ be the subgraph of $T$ induced by $V'$. Is $T'$ necessarily a minimum spanning tree of the subgraph $G'$ of $G$ induced by $V'$? If so, prove it; otherwise, give a counterexample.

• 中文翻译： 设 $T$ 是图 $G = (V, E)$ 的一棵最小生成树，且 $V'$ 是 $V$ 的一个子集。设 $T'$ 是由 $V'$ 在 $T$ 中导出的子图。$T'$ 是否一定是由 $V'$ 在 $G$ 中导出的子图 $G'$ 的最小生成树？如果是，请予以证明；如果不是，请举出一个反例。

• 核心考点： 子图诱导（Induced Subgraph）下的 MST 保持性问题。

• 解题思路提示 (Hint)：

  1. 试着画一个极其简单的图，比如三个顶点呈线性或环状排列。
  2. 例如：$A - B - C$ 权重分别为 1 和 2，同时存在一条 $A - C$ 权重为 3 的边。
  3. 选择一个顶点子集 $V' = \{A, C\}$。看看在原树 $T$ 中，它们之间是否还有边？在原图中，它们是否有直接相连的更短的边？

【解答】：不一定（结论不成立）。

【反例说明】：

1. 设无向图 $G$ 包含 3 个顶点 $V = \{1, 2, 3\}$，边集及权重如下：
   • $w(1, 2) = 1$
   • $w(2, 3) = 1$
   • $w(1, 3) = 3$
2. 显而易见，$G$ 的唯一最小生成树 $T$ 包含边 $\{(1, 2), (2, 3)\}$，总权重为 2。
3. 现在我们取顶点子集 $V' = \{1, 3\}$。
4. 那么由 $V'$ 导出的原图子图 $G'$ 包含顶点 $\{1, 3\}$ 以及它们之间的边 $(1, 3)$（权重为 3）。因此 $G'$ 的 MST 显然必须包含边 $(1, 3)$。
5. 然而，由 $V'$ 在树 $T$ 中导出的子图 $T'$，由于 $T$ 中没有直接连接 $1$ 和 $3$ 的边（因为在 $T$ 中它们是通过 $2$ 间接相连的，而 $2 \notin V'$），所以子图 $T'$ 根本不包含任何边。
6. 一个没有边的子图 $T'$ 显然连连通都做不到，更不可能是 $G'$ 的最小生成树。

【追加思考】：如果题目改成“把 $G$ 分裂成两个由割定义的子图”，结论会如何？在学习图算法时，一定要小心这类“局部最优”不等于“全局诱导最优”的陷阱。

第二阶段：Kruskal 与 Prim 算法执行细节 (21.2 节)

这部分题目针对具体算法的运行步骤和边界场景，能切实检验你是否掌握了两个算法的底层逻辑。

✍️ 练习 21.2-1 & 21.2-2 (算法执行过程追踪)

• 英文原题意图： 给定一个具体的带权图（通常是 CLRS 图 21.4，包含 9 个顶点 $a$ 到 $i$），要求分别写出 Kruskal 和 Prim 算法加入边的顺序。
• 练习建议： 由于你手写笔记中记录了 Prim 和 Kruskal 的 Demo 逻辑，请用以下这个经典的 5 点图做一次手算演练。

       [B]
      /   \
     3     1
    /       \
  [A]—— 4 ——[C]
    \       /
     5     2
      \   /
       [D]

【任务 1：Kruskal 算法演练】 请写出边排序后的列表，并依次判断是否加入，记录并查集的变化过程。

【任务 2：Prim 算法演练（从 A 出发）】 请记录优先队列（Fringe）中每个顶点的 distTo 变化，以及每次被 delMin 取出的顶点。

任务 1 (Kruskal) 步骤拆解：

1. 边按权重排序：
   • $B-C$ (1)
   • $C-D$ (2)
   • $A-B$ (3)
   • $A-C$ (4)
   • $A-D$ (5)
2. 依次处理：
   • 取出 $B-C$ (1)：并查集连通性检查：$B, C$ 不连通。加入 MST，合并 $\{B, C\}$。
   • 取出 $C-D$ (2)：并查集连通性检查：$C, D$ 不连通。加入 MST，合并 $\{B, C, D\}$。
   • 取出 $A-B$ (3)：并查集连通性检查：$A, B$ 不连通。加入 MST，合并 $\{A, B, C, D\}$。
   • 此时已加入 $V-1 = 3$ 条边，算法可以提前结束。
3. 最终 MST 边集：$\{(B,C), (C,D), (A,B)\}$，总权重为 6。

任务 2 (Prim 从 A 出发) 步骤拆解：

1. 初始化：
   • distTo[A] = 0, 其它为 $\infty$。
   • Fringe PQ: [(A:0), (B:∞), (C:∞), (D:∞)]
2. 第 1 轮：
   • delMin() 取出 $A$。标记 $A$ 已访问。
   • 松弛 $A$ 的邻居：
     • $B$: $A-B(3) < \infty \Rightarrow$ 更新 distTo[B] = 3
     • $C$: $A-C(4) < \infty \Rightarrow$ 更新 distTo[C] = 4
     • $D$: $A-D(5) < \infty \Rightarrow$ 更新 distTo[D] = 5
   • Fringe PQ: [(B:3), (C:4), (D:5)]
3. 第 2 轮：
   • delMin() 取出 $B$。标记 $B$ 已访问。
   • 松弛 $B$ 的邻居中未访问的点（$C$ 和 $D$）：
     • $C$: $B-C(1) < 4$（原 distTo[C]） $\Rightarrow$ 更新 distTo[C] = 1, edgeTo[C] = B-C
   • Fringe PQ: [(C:1), (D:5)]
4. 第 3 轮：
   • delMin() 取出 $C$。标记 $C$ 已访问。
   • 松弛 $C$ 的邻居中未访问的点（仅剩 $D$）：
     • $D$: $C-D(2) < 5$（原 distTo[D]） $\Rightarrow$ 更新 distTo[D] = 2, edgeTo[D] = C-D
   • Fringe PQ: [(D:2)]
5. 第 4 轮：
   • delMin() 取出 $D$。标记 $D$ 已访问。Fringe 为空，结束。
6. 最终 MST 边集：$\{(A,B), (B,C), (C,D)\}$。

✍️ 练习 21.2-3 (当边权是小范围整数时的优化)

• 英文原题：

  Suppose that all edge weights in a graph $G$ are integers in the range from $1$ to $|V|$. How fast can you make Kruskal’s algorithm run? What if the edge weights are integers in the range from $1$ to some constant $W$?

• 中文翻译： 假设图 $G$ 中所有边的权重都是介于 $1$ 到 $|V|$ 之间的整数。你能将 Kruskal 算法的运行时间优化到多快？如果边的权重是介于 $1$ 到某个常数 $W$ 之间的整数，结果又会如何？

• 核心考点： 你在手写笔记里提到的“预排序情况下的 Kruskal 复杂度推导”。这里考查利用非比较排序（如计数排序/基数排序）替代二叉堆来突破 $O(E \log E)$ 的限制。

• 解题思路提示 (Hint)：

  1. Kruskal 算法的传统瓶颈在边排序，需要 $O(E \log E)$。
  2. 如果权重范围限制在 $[1, V]$，我们可以使用计数排序 (Counting Sort)。回想一下计数排序的时间复杂度是多少？
  3. 如果权重范围限制在 $[1, W]$ 且 $W$ 为常数，同样可以用计数排序。排序后，Kruskal 算法的瓶颈会变成什么？

【深度解析】：

1. 当边权限制在 $[1, V]$ 时：
   • 排序阶段：我们可以使用计数排序 (Counting Sort) 对 $E$ 条边进行排序。因为最大值 $V \le E$（由于图是连通的），计数排序的时间复杂度为 $O(E + V) = O(E)$。
   • 并查集阶段：在边有序后，我们依次取出边进行 connected 和 union 操作。总共会进行 $E$ 次 connected 和 $V-1$ 次 union 操作。
   • 使用带有路径压缩和按秩合并的并查集，这些操作的总耗时为 $O(E \alpha(V))$。
   • 总结运行时间：排序 $O(E)$ + 并查集 $O(E \alpha(V))$ = $O(E \alpha(V))$。
2. 当边权限制在 $[1, W]$（$W$ 为常数）时：
   • 排序阶段：同样使用计数排序，时间复杂度为 $O(E + W)$。因为 $W$ 是常数，所以排序时间为 $O(E)$。
   • 并查集阶段：依然是 $O(E \alpha(V))$。
   • 总结运行时间：$O(E \alpha(V))$。

💡 笔记联动：这完美应证了你手写笔记最后一页写到的 “Kruskal’s with pre-sorted edges runs in $O(E \log^* V)$”（注：$\log^* V$ 与反阿克曼函数 $\alpha(V)$ 在渐进意义上都代表极缓慢增长的准常数）。

第三阶段：经典高阶思考题 (次小生成树)

为了让你的 MST 理论认知达到卓越水平，建议攻克这道 CLRS 经典的课后大题。

✍️ 思考题 21-1：次小生成树 (Second-best Minimum Spanning Tree)

• 背景介绍： 给定一个带权无向连通图 $G = (V, E)$。我们知道它可能有多棵生成树。其中总权重最小的称为最小生成树 (MST)。而总权重第二小的生成树（可以与 MST 权重相等，只要它是不同的边集组合）被称为次小生成树 (Second-best MST)。
• 问题设计：
  1. 设 $T$ 是 $G$ 的唯一一棵 MST。证明：次小生成树 $T'$ 一定可以通过“替换一条边”从 $T$ 得到。也就是说，存在一条边 $u \in T$ 和一条边 $v \notin T$，使得 $T' = T - \{u\} \cup \{v\}$。
  2. 给出高效算法的系统设计思路：如何在 $O(V^2)$ 的时间内找到这棵次小生成树？
• 核心考点： 生成树的性质变换、路径上最大边查询。
• 解题思路提示 (Hint)：
  1. 对于第一问：利用代数结构（或反证法），假设 $T'$ 与 $T$ 有多于一条边的差异，证明可以用更小的一步替换来构造出介于其间的生成树。
  2. 对于第二问：如果我们把任意一条不在 $T$ 中的边 $(u, v)$（权重为 $w(u, v)$）加入 $T$，会形成环。为了让新生成的树权重增加最少，我们应该删去该环上权重最大的一条边（设为 $max[u, v]$）。
  3. 那么替换后的新权重为 $w(T) - w(max[u, v]) + w(u, v)$。我们需要遍历所有不在 $T$ 中的边，找到使这个增量最小的替换。
  4. 如何预先计算出树 $T$ 中任意两点 $u, v$ 路径上的最大边权重 $max[u, v]$？可以在树 $T$ 上运行一次 DFS/BFS 吗？

第一问证明：

假设 $T$ 是 $G$ 的唯一 MST，$T_{2nd}$ 是次小生成树。 设距离（不同边的数量）最小的次小生成树不满足只相差一条边的条件，即 $T_{2nd}$ 与 $T$ 相差 $k$ 条边（$k \ge 2$）。

1. 既然 $T_{2nd} \neq T$，必定存在一条边 $e_0 \in T_{2nd}$ 且 $e_0 \notin T$。
2. 将 $e_0$ 加入 $T$ 会产生一个唯一的环 $C$。环 $C$ 中必定存在一条边 $e_1 \in T$ 且 $e_1 \notin T_{2nd}$。
3. 根据 MST 的性质，必有 $w(e_1) \le w(e_0)$。
4. 我们构造一棵新树 $T^* = T_{2nd} - \{e_0\} \cup \{e_1\}$。这棵新树与 $T$ 的差异减少到了 $k-1$ 条边。
5. 且 $w(T^*) = w(T_{2nd}) - w(e_0) + w(e_1) \le w(T_{2nd})$。
6. 因为 $T$ 是唯一的 MST，且 $T^*$ 也是一棵生成树，所以：
   • 若 $w(T^*) < w(T_{2nd})$，则 $T_{2nd}$ 根本不是次小生成树（因为 $T^*$ 比它更小且不等于 $T$），产生矛盾。
   • 若 $w(T^*) = w(T_{2nd})$，则 $T^*$ 是一棵与 $T$ 差异更小（$k-1$ 条边）的次小生成树。
7. 通过数学归纳，我们总能将差异收缩到刚好 1 条边。因此，次小生成树必然可以通过从 $T$ 中移去一条边 $u$ 并加入一条非树边 $v$ 得到。$\blacksquare$

第二问算法设计思路：

基于第一问的结论，次小生成树的值为：

$\min_{(u, v) \notin T} \{ w(T) - w(max[u, v]) + w(u, v) \}$

其中 $max[u, v]$ 是树 $T$ 中 $u$ 到 $v$ 唯一路径上的最大权重边。

高效算法步骤：

1. 第一步：运行 Prim 或 Kruskal 算法求出 MST $T$。时间开销：$O(E \log V)$。
2. 第二步：对于树 $T$ 中的每一个顶点 $u$，进行一次 DFS：
   • 这次 DFS 只在树 $T$ 的边上进行，用来寻找从 $u$ 出发到达其它所有节点 $v$ 的路径。
   • 在 DFS 遍历过程中，维护并记录路径上的最大权重边 $max[u, v]$。
   • 单次 DFS 耗时 $O(V)$（因为树只有 $V-1$ 条边）。对所有 $V$ 个顶点各做一次，总耗时为 $O(V^2)$。
3. 第三步：遍历所有不在 $T$ 中的边 $(u, v) \in E \setminus T$：
   • 计算替换代价：$\Delta = w(u, v) - w(max[u, v])$。
   • 找出所有边中 $\Delta$ 最小的值。
   • 这一步最多遍历 $E$ 条边，单次查询 $max[u, v]$ 是 $O(1)$ 的，因此耗时 $O(E)$。
4. 第四步：次小生成树的权重即为 $w(T) + \min(\Delta)$。

【总时间复杂度】：

$O(E \log V + V^2 + E) = O(V^2)$

在稠密图中，这比直接暴力穷举所有树的替换要高效得多！