6.4 最小生成树

最小生成树的性质，Prim 算法与 Kruskal 算法的过程、实现要点与复杂度对比。

最小生成树的概念

一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。

对于一个带权连通无向图 $G = (V, E)$，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 $\mathfrak{R}$ 为 $G$ 的所有生成树的集合，若 $T$ 为 $\mathfrak{R}$ 中边的权值之和最小的生成树，则 $T$ 称为 $G$ 的最小生成树（Minimum Spanning Tree，MST）。

构造最小生成树的算法大多利用了如下性质（MST 性质）：假设 $G = (V, E)$ 是一个带权连通无向图，$U$ 是顶点集 $V$ 的一个非空子集。若 $(u, v)$ 是一条具有最小权值的边，其中 $u \in U$，$v \in V - U$，则必存在一棵包含边 $(u, v)$ 的最小生成树。

基于该性质的最小生成树算法主要有 Prim 算法和 Kruskal 算法，它们都基于贪心算法的策略。

Prim 算法

Prim（普里姆）算法的执行非常类似于寻找图的最短路径的 Dijkstra 算法。

1void Prim(G, T) {
2    T = ∅;                       // 初始化空树
3    U = {w};                     // 添加任意一个顶点 w
4    while ((V - U) != ∅) {       // 若树中不含全部顶点
5        设 (u, v) 是使 u ∈ U 与 v ∈ (V - U)，
6            且权值最小的边;
7        T = T ∪ {(u, v)};        // 边归入树
8        U = U ∪ {v};             // 顶点归入树
9        更新 V - U 中各顶点到 U 的最小代价 lowcost[];
10    }
11}

实现时用两个辅助数组：lowcost[] 记录 $V - U$ 中各顶点到 $U$ 的最小边权，adjvex[]（或 closest[]）记录对应边在 $U$ 中的端点。每并入一个新顶点 $k$，都用 $k$ 到其余顶点的边权去更新 lowcost[]。

时间复杂度 $O(|V|^2)$，不依赖于 $|E|$，因此它适用于求解边稠密的图的最小生成树。虽然采用其他方法能改进 Prim 算法的时间复杂度，但增加了实现的复杂性。

Kruskal 算法

与 Prim 算法从顶点开始扩展最小生成树不同，Kruskal（克鲁斯卡尔）算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

1void Kruskal(V, T) {
2    T = V;                       // 初始化树 T，仅含顶点
3    numS = n;                    // 连通分量数
4    while (numS > 1) {           // 若连通分量数大于 1
5        从 E 中取出权值最小的边 (v, u);
6        if (v 和 u 属于 T 中不同的连通分量) {
7            T = T ∪ {(v, u)};    // 将此边加入生成树中
8            numS--;              // 连通分量数减 1
9        }                        // 否则舍弃（会形成回路）
10    }
11}

在 Kruskal 算法中，最坏情况需要对 $|E|$ 条边各扫描一次。通常在 Kruskal 算法中，采用堆来存放边的集合，因此每次选择最小权值的边只需 $O(\log_2|E|)$ 的时间。此外，由于生成树 T 中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集来描述 T，从而构造 T 的时间复杂度为 $O(|E| \log_2 |E|)$。因此，Kruskal 算法适合于边稀疏而顶点较多的图。

两种算法的对比

即时练习