最小生成树

Views: --

给定连通带权无向图，最小生成树（MST）是在连接全部顶点的所有生成树中，总边权最小的一棵。

生成树有 ∣V∣−1|V|-1 条边、连通且无环。MST 优化的是整棵树的边权总和，不是从某个源点到各点的距离。

1. 割、轻边与安全边

割 (S,V−S)(S,V-S) 把顶点分成两部分。一个端点在 SS、另一个端点在 V−SV-S 的边称为跨越该割。

跨越某个割的最小权边称为轻边。若当前已选边集 AA 没有跨越这个割，即该割尊重 AA，那么一条跨割轻边是 AA 的安全边：把它加入后，仍存在某棵 MST 包含新的 AA。

2. 割性质为什么成立

设某棵包含 AA 的 MST TT 没有轻边 ee。向 TT 加入 ee 会形成唯一环；这个环必须还有一条边 e′e' 跨越同一个割。

因为 ee 是轻边，w(e)≤w(e′)w(e)\le w(e')。删掉 e′e' 后仍是一棵生成树，权重不增，并且包含 A∪{e}A\cup\{e\}。所以总能找到一棵 MST 接纳这条安全边。

Prim 和 Kruskal 的差别，只在于每次选择了哪个“尊重当前边集的割”。

3. Kruskal 算法

Kruskal 从许多单点树出发，按边权从小到大尝试连接不同连通分量：

sort edges by weight ascending
make each vertex its own set
for (u, v) in sorted edges:
    if find(u) != find(v):
        select (u, v)
        union(u, v)

并查集负责判断加边是否成环。路径压缩和按秩合并使并查集操作近似常数，整体由排序主导：

O(Elog⁡E)=O(Elog⁡V).O(E\log E)=O(E\log V).

它尤其适合边列表和稀疏图。

4. Prim 算法

Prim 始终维护一棵正在扩大的树。对每个树外顶点 vv，记录它连接当前树的最小边权 key[v]，每次取 key 最小的顶点加入：

key[root] = 0
put all vertices into a min-priority queue
while queue is not empty:
    u = extractMin()
    for each (u, v, w):
        if v is outside tree and w < key[v]:
            key[v] = w
            parent[v] = u

二叉堆加邻接表时为 O(Elog⁡V)O(E\log V)；邻接矩阵朴素实现为 O(V2)O(V^2)，在稠密图中反而很合适。

5. 权重相同时怎么办

MST 可能不唯一。Kruskal 的同权边顺序或 Prim 的起点不同，可能得到不同树，但最小总权重相同。

若所有边权两两不同，则 MST 唯一；反过来不成立，边权有重复也可能仍唯一。

6. 非连通图

非连通图不存在覆盖全部顶点的生成树。Kruskal 会得到每个连通分量各自的 MST，合称最小生成森林；Prim 则需要从每个未访问分量重新启动。

7. 与最短路径树的区别

最短路径树最小化源点到每个点的路径长度；MST 最小化所有选中边的总和。一棵 MST 未必给出源点最短路，一棵最短路径树也未必是 MST。

8. 做题检查

  • 图必须是无向图；有向图对应最小树形图，不是普通 MST；
  • 负边不妨碍 MST，仍按权重处理；
  • Kruskal 判环要看连通分量，不是只检查两个端点是否直接相邻；
  • Prim 更新的是连接当前树的单条最小边，不是从根累计的路径距离。

评论