最小生成树

from 算法导论（CLRS）

在本章中，我们将讨论两种最小生成树的贪心算法 —— Kruskal 算法和 Prim 算法。对于最小生成树问题来说，我们可以证明，某些贪心策略确实能够找到一个全局最优的解决方案。

23.1 最小生成树的形成

假定一个连通无向图 $G = (V, E)$ 和权重函数 $w : E \rightarrow \mathbb{R}$ ，我们希望找出图 $G$ 的一棵最小生成树。本章讨论的两种算法都使用贪心策略来解决这个问题，但它们使用贪心策略的方式却有所不同。

这个贪心策略可以由下面的通用方法来表述。该通用方法在每个时刻生长最小生成树的一条边，并在整个策略的实施过程中，管理一个遵守下述循环不变式的边集合 $A$ ：

在每遍循环之前，$A$ 是某棵最小生成树的一个子集。

在每一步，我们要做的事情是选择一条边 $(u,v)$，将其加入集合 $A$ 中，使得 $A$ 不违反循环不变式 —— $A \cup\{(u, v)\}$ 也是某棵最小生成树的子集。由于我们可以安全地将这条边加入到集合 $A$ 而不会破坏 $A$ 的循环不变式，因此，称这样的边为集合 $A$ 的安全边。

在本节接下来的内容，我们将介绍辨认安全边的规则。在下一节则讨论使用这种规则来快速寻找安全边的两个算法。

无向图 $G = (V,E)$ 的一个切割 $(S, V-S)$ 是集合 $V$ 的一个划分，如下图所示。

如果一条边 $(u,v) \in E$ 的一个端点位于集合 $S$，另一个端点位于集合 $V-S$，则称该条边横跨切割 $(S, V-S)$。如果集合 $A$ 中不存在横跨该切割的边，则称该切割尊重集合 $A$。在横跨一个切割的所有边中，权重最小的边称为轻量级边。

上图中，加了阴影的边属于子集 $A$：切割 $(S,V-S)$ 尊重集合 $A$。

用来辨认安全边的规则由如下定理给出：

定理 23.1 设 $G = (V,E)$ 是一个在边 $E$ 上定义了实数值权重函数 $w$ 的连通无向图。设集合 $A$ 为 $E$ 的一个子集，且 $A$ 包括在图 $G$ 的某棵最小生成树中，设 $(S, V-S)$ 是图 $G$ 中尊重集合 $A$ 的任意一个切割，又设 $(u,v)$ 是横跨切割 $(S, V-S)$ 的一条轻量级边。那么边 $(u,v)$ 对于集合 $A$ 是安全的。

23.2 节中的两个算法将使用下列推论：

推论 23.2 设 $G = (V,E)$ 是一个在边 $E$ 上定义了实数值权重函数 $w$ 的连通无向图。设集合 $A$ 为 $E$ 的一个子集，且 $A$ 包括在图 $G$ 的某棵最小生成树中，并设 $C = (V_c, E_c)$ 为森林 $G_A = (V, A)$ 中的一个连通分量（树）。如果边 $(u,v)$ 是连接 $C$ 和 $G_A$ 中某个其他连通分量的一条轻量级边，则边 $(u,v)$ 对于集合 $A$ 是安全的。

23.2 Kruskal 算法和 Prim 算法

Kruskal 算法

Prim 算法

Prim 算法初始选择一个结点，在算法每一步，树中的结点就决定了图的一个切割，横跨该切割的一条轻量级边被加入到树中。