算法（H）笔记——最小生成树

最小生成树

基本思想

最小生成树问题具有最优子结构。

可以用 cut-and-paste 反证来理解：如果一个最小生成树中的某个局部结构不是对应子问题的最优解，那么就可以把这个局部结构替换成更优结构，从而得到权重更小的生成树，这与原树是最小生成树矛盾。

课堂中还提到最小生成树存在重叠子问题，因此从形式上可以考虑动态规划。但更重要、更常用的是贪心性质。

贪心性质

对于一个已经形成的子图 \(G'\)，从 \(G'\) 到 \(V-G'\) 之间的最短边一定属于某棵最小生成树。

反证思路：

设这条最短边为 \((u,v)\)。如果最小生成树中不包含 \((u,v)\)，那么在树中一定存在一条从 \(u\) 到 \(v\) 的路径。沿这条路径找到第一条跨出当前子图的边，用 \((u,v)\) 替换它，就可以使总权重减小或不增，从而得到另一棵最小生成树。

这个思想对应 Prim 算法。

常见问题

如何保证 Prim 算法不会成环

Prim 算法每次从已经加入树的点集向外选择一条连接到未加入点的最小边。

由于新加入的边总是连接“树内点”和“树外点”，所以每次只会增加一个新顶点，不会在已有树内部连接两个点，因此不会成环。

Dijkstra 和 Prim 的区别

两者形式很像，都维护一个优先队列，也都会反复取出 key 最小的点。

区别在于 key 的含义不同：

• Dijkstra 中，\(v.d\) 表示从源点 \(s\) 到 \(v\) 的当前最短路径估计。
• Prim 中，\(v.key\) 表示把 \(v\) 连接到当前生成树所需的最小边权。

因此：

• Dijkstra 求的是从一个源点到其他点的最短路径。
• Prim 求的是覆盖所有点且总边权最小的生成树。

U23.1：安全边与切割

安全边

若 \(A\) 是某棵最小生成树的子集，且向 \(A\) 中加入边 \((u,v)\) 后，\(A \cup \{(u,v)\}\) 仍然是某棵最小生成树的子集，则称 \((u,v)\) 是 \(A\) 的安全边。

切割

切割是将图的顶点集合 \(V\) 分成两个点集：

\[ (S, V-S) \]

横跨

若一条边的两个端点分别位于切割的两个不同部分，则称这条边横跨该切割。

切割尊重边集 \(A\)

如果 \(A\) 中没有任何一条边横跨切割 \((S,V-S)\)，则称该切割尊重边集 \(A\)。

轻量级边

在所有横跨某个切割的边中，权重最小的边称为轻量级边。

轻量级边不一定唯一。

定理 23.1

已知边集 \(A\) 是某棵最小生成树的子集。设切割 \((S,V-S)\) 尊重 \(A\)。若边 \((u,v)\) 是横跨该切割的一条轻量级边，则 \((u,v)\) 是 \(A\) 的安全边。

证明思路

设 \(T\) 是一棵包含 \(A\) 的最小生成树。

如果 \(T\) 中已经包含 \((u,v)\)，则 \((u,v)\) 显然是安全边。

否则，将 \((u,v)\) 加入 \(T\) 后，会和 \(T\) 中从 \(u\) 到 \(v\) 的唯一路径形成一个环。

由于 \((u,v)\) 横跨切割 \((S,V-S)\)，所以这个环中一定还存在另一条边 \((x,y)\) 也横跨该切割。

从 \(T\) 中删去 \((x,y)\) 会得到两个连通分量，再加入 \((u,v)\) 可以把这两个连通分量重新连起来。因此：

\[ T'=T-\{(x,y)\}+\{(u,v)\} \]

仍然是一棵生成树。

由于 \((u,v)\) 是横跨该切割的轻量级边，所以：

\[ w(u,v) \le w(x,y) \]

因此：

\[ w(T') \le w(T) \]

而 \(T\) 已经是最小生成树，所以 \(T'\) 也是最小生成树。

又因为切割尊重 \(A\)，所以 \(A\) 中的边都不横跨该切割，因此 \((x,y) \notin A\)。删去 \((x,y)\) 不会破坏 \(A\)，于是 \(A \cup \{(u,v)\}\) 仍然包含在某棵最小生成树 \(T'\) 中。

所以 \((u,v)\) 是 \(A\) 的安全边。

U23.2：两种贪心算法

最小生成树的两个经典算法都是贪心算法：

1. Kruskal 算法
2. Prim 算法

Kruskal 算法

Kruskal 算法的思想：

1. 按边权从小到大考虑所有边。
2. 如果加入当前边不会形成环，就加入。
3. 如果会形成环，就跳过。
4. 最后得到最小生成树。

伪代码

MST-KRUSKAL(G, w)
1  A = ∅
2  for each vertex v ∈ G.V
3      MAKE-SET(v)
4  sort the edges of G.E into nondecreasing order by weight w
5  for each edge (u, v) ∈ G.E, taken in nondecreasing order by weight
6      if FIND-SET(u) ≠ FIND-SET(v)
7          A = A ∪ {(u, v)}
8          UNION(u, v)
9  return A

复杂度

初始化并查集：

\[ O(V) \]

对所有边排序：

\[ O(E\lg E) \]

依次检查每条边是否可以合并，使用并查集：

\[ O(E\alpha(V)) \]

其中 \(\alpha(V)\) 是反 Ackermann 函数，可以近似看作常数。

因此总复杂度为：

\[ O(E\lg E) \]

对于简单图，有：

\[ E < V^2 \]

所以也可以写成：

\[ O(E\lg V) \]

Prim 算法

Prim 算法的思想：

1. 从一个根结点 \(r\) 开始。
2. 维护当前已经加入生成树的点集。
3. 每次选择一条连接树内点和树外点的最小边。
4. 不断扩展，直到所有点都加入生成树。

优先队列中，每个结点维护它到当前树中任一结点的最小距离。

伪代码

MST-PRIM(G, w, r)
1  for each u ∈ G.V
2      u.key = ∞
3      u.π = NIL
4  r.key = 0
5  Q = G.V
6  while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9          if v ∈ Q and w(u, v) < v.key
10             v.π = u
11             v.key = w(u, v)

复杂度分析

若使用二叉堆优先队列：

建堆：

\[ O(V) \]

EXTRACT-MIN 共执行 \(V\) 次，每次代价为 \(O(\lg V)\)，因此：

\[ O(V\lg V) \]

更新所有邻接边的 key，总共考虑约 \(2E\) 次边，DECREASE-KEY 代价为 \(O(\lg V)\)，因此：

\[ O(E\lg V) \]

总复杂度为：

\[ O(V\lg V + E\lg V) \]

若图连通，则 \(E \ge V-1\)，因此可以简化为：

\[ O(E\lg V) \]

若使用斐波那契堆：

• EXTRACT-MIN 的摊还代价为 \(O(\lg V)\)。
• DECREASE-KEY 的摊还代价为 \(O(1)\)。

总复杂度为：

\[ O(E+V\lg V) \]

稀疏图与稠密图

课堂备注：

• 对于简单图或 \(E<V^2\) 的情况，可以使用优先队列实现 Prim。
• 对于稠密图，可以使用双循环遍历节点的实现方式。