CS61B 课程笔记（Lecture 30 Minimum Spanning Trees)

最小生成树 (Minimum Spanning Tree, MST) 详解

1. 最小生成树的定义

最小生成树是一个加权图中的边的一个子集，使得：

• 包含所有的顶点（即图是“生成”的）
• 没有环（即图是“树”的）
• 边的总权重最小

2. 切割性质 (Cut Property)

• 切割定义：将图的节点划分为两个非空集合。
• 交叉边：连接这两个集合的边。

切割性质：对于任意的切割，最小权重的交叉边必定在最小生成树中。

证明：

• 假设最小交叉边 (\(e\)) 不在生成树中。
• 如果将 (\(e\)) 添加到生成树中，会形成一个环。此时，环中必然有另一条交叉边 (\(f\))，我们可以去掉 (\(f\)) 而保留 (\(e\))，从而形成一个权重更小的生成树。这与假设矛盾，因此切割性质成立。

3. Prim 算法

Prim 算法步骤：

1. 从任意一个节点开始。
2. 重复添加一条与已构建生成树相连的最短边。
3. 直到有 (\(V-1\)) 条边为止（(\(V\)) 为节点总数）。

为何有效：

• 每次添加的边都是穿过当前生成树和剩余节点的最小边。
• 根据切割性质，这条边一定在最小生成树中。

实现：

• 该算法的运行机制与 Dijkstra 算法相似，但 Prim 算法关注的是与已构建生成树的距离。

时间复杂度：

• (\(O((|V| + |E|) \log |V|)\))

4. Kruskal 算法

Kruskal 算法步骤：

1. 将所有边按权重从小到大排序。
2. 逐条检查边，若添加这条边不形成环，则加入生成树。
3. 直到有 (\(V-1\)) 条边为止。

为何有效：

• 每次添加的边都是当前最小的交叉边。
• 因为只有不形成环的边才能被加入，保证了生成树的特性。

时间复杂度：

• 未排序边：(\(O(|E| \log |E|)\))
• 已排序边：(\(O(|E| \log^* |V|)\))

5. 比较 Prim 与 Kruskal 算法

• 结果：两种算法得到的最小生成树可能不同，但都是最优解，且权重总和相同。
• 使用情况：Prim 适用于稠密图，Kruskal 适用于稀疏图。

6. 章节总结

• 最小生成树 (MST) 是图中连接所有顶点的权重最小的边集。
• 切割性质：给定任何切割，最小权重的交叉边在 MST 中。
• Prim 算法：构建 MST 的过程与 Dijkstra 类似，时间复杂度为 (\(O((|V| + |E|) \log |V|)\))。
• Kruskal 算法：通过排序边来构建 MST，时间复杂度为 (\(O(|E| \log |E|)\))（未排序边）或 (\(O(|E| \log^* |V|)\))（已排序边）。