4.4 最小生成树：Prim 与 Kruskal

4.4 最小生成树：Prim 与 Kruskal

本节摘要：连通无向图里挑出 V-1 条边把所有顶点连起来且总权最小，这就是最小生成树（MST）。Prim 从一个顶点出发"从点生长"，用堆每轮吸收离树最近的顶点，适合稠密图；Kruskal 把边按权排序"从边生长"，用并查集拒绝成环边，适合稀疏图。两者都建立在同一条贪心定理上，且答案总权唯一（树形可不同）。

最省的骨架：问题与贪心定理

铺光缆连接若干楼宇、修公路连通村镇、电路布线连通元件——共同点是：只要连通就好，追求总成本最小。数学模型即最小生成树：无向连通图 G 的一个子图，包含全部 V 个顶点、恰好 V-1 条边、无环，且边权总和最小。

为什么"恰好 V-1 条"？连通 V 个点至少要 V-1 条边（再少必不连通）；一旦有 V-1 条边且连通，必然无环（无环连通图的边数恰为 V-1，这本身就是树的定义）。所以 MST 是"连通"这个需求的极限省法。

两条贪心路线都吃同一条定理（切割定理）：把顶点分成"已选"与"未选"两堆，横跨两堆的最小边必属于某棵 MST。Prim 每轮兑现一次这条定理（从树内望向树外，挑最便宜的横跨边）；Kruskal 则在全局排序的边上间接兑现。

Kruskal：边从小到大，见环就跳过

# Kruskal：边排序 + 并查集判环（并查集为极简版，7.1 节正式修炼）
def kruskal(n, edges):
    parent = list(range(n))                  # 每点自成一阵营

    def find(x):                             # 查阵营首领
        while parent[x] != x:
            x = parent[x]
        return x

    def union(a, b):                         # 两阵营合并
        ra, rb = find(a), find(b)
        if ra == rb:
            return False                     # 同一阵营：接边必成环
        parent[ra] = rb
        return True

    picked, total = [], 0
    for w, u, v in sorted(edges):            # 边按权从小到大
        if union(u, v):
            picked.append((u, v, w))
            total += w
            print(f"接入边 {u}-{v} 权 {w}，累计 {total}")
        else:
            print(f"拒绝边 {u}-{v} 权 {w}（成环）")
        if len(picked) == n - 1:             # V-1 条边即完工
            break
    return picked, total

E = [(2, 0, 1), (6, 0, 3), (3, 1, 2), (8, 1, 3), (5, 2, 3), (9, 3, 4)]
_, total = kruskal(5, E)
print("最小生成树总权 =", total)
# 输出：
# 接入边 0-1 权 2，累计 2
# 接入边 1-2 权 3，累计 5
# 接入边 2-3 权 5，累计 10
# 拒绝边 0-3 权 6（成环）
# 拒绝边 1-3 权 8（成环）
# 接入边 3-4 权 9，累计 19
# 最小生成树总权 = 19
​

Kruskal 的账：排序 O(E log E)，判环近乎 O(1)（并查集路径压缩后），总复杂度 O(E log E)。边数是主导——稀疏图（E 与 V 同量级）时它几乎就是一次排序的价钱。

Prim：从点生长，堆里挑最近的门外汉

Prim 换个方向：树从起点长出来，每轮用堆挑出"离树最近"的门外顶点吸收进来。像滚雪球，也像 Dijkstra 的近亲——两者都是堆驱动的贪心，区别只在比较的量：Dijkstra 比"离源点的总距离"，Prim 比"离树的直接边权"。

# Prim：堆驱动，从顶点 0 开始生长
import heapq

def prim(n, edges, start=0):
    adj = [[] for _ in range(n)]
    for w, u, v in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))

    in_tree = [False] * n
    heap = [(0, start, -1)]                  # （边权， 顶点， 来源）
    total, picked = 0, []
    while heap:
        w, u, frm = heapq.heappop(heap)
        if in_tree[u]:
            continue                         # 已在树中：过期堆项
        in_tree[u] = True
        total += w
        if frm >= 0:
            picked.append((frm, u, w))
            print(f"吸收 {u}：经边 {frm}-{u} 权 {w}，累计 {total}")
        for v, wv in adj[u]:
            if not in_tree[v]:
                heapq.heappush(heap, (wv, v, u))
    return picked, total

_, total = prim(5, E)
print("Prim 总权 =", total)
# 输出：
# 吸收 1：经边 0-1 权 2，累计 2
# 吸收 2：经边 1-2 权 3，累计 5
# 吸收 3：经边 2-3 权 5，累计 10
# 吸收 4：经边 3-4 权 9，累计 19
# Prim 总权 = 19
​

同一张图，两条路线选出的边完全一致（本题树形唯一），总权都是 19。Prim 的账是 O(E log V)（堆里只放"树外"顶点的候选边）。

⚠️ 常见坑：把 MST 当"最短路径树"。MST 最小化的是边权总和，不是"各点到某源点的距离之和"。同一个图里，MST 上两点的路径可能远比最短路径绕——通勤走 Dijkstra，铺缆走 MST，两码事。

💡 关键直觉：Kruskal 的拒绝逻辑（同堆即成环）与 Prim 的吸收逻辑（挑最便宜的横跨边）是切割定理的一体两面。证明思路：若横跨最小边不在某棵 MST 里，换入它总能让总权不增。

走火入魔：贪心也能错场合

**事故一：图不连通还想求 MST。**Kruskal 跑完发现选不满 V-1 条边，说明图根本不连通，此时正确产物是"最小生成森林"（每个分量一棵树）。拿残缺的边集硬算总权没有意义。先跑 4.2 节的连通分量检查，再谈 MST。

**事故二：把 Prim 堆里的过期项当新鲜事。**同一顶点会被多个树内邻居反复推进堆，弹出时必须检查 in_tree 跳过，与 4.3 节 Dijkstra 的惰性删除同一门功课。忘了跳过，边会被重复计入总权。

延伸一句：MST 还是聚类与近似的工具——删掉 MST 里最大的 k 条边，得到 k+1 个簇，是层次聚类的经典近似；旅行商问题在度量空间也有基于 MST 的两倍近似解。兵器谱上它的排位远不止"铺缆"。

本节要点回顾

• MST 定义：V 个顶点、V-1 条边、连通无环、总权最小；切割定理是两条贪心路线的共同靠山；
• Kruskal 从边生长：按权排序、并查集判环，O(E log E)，稀疏图首选，顺产生成森林；
• Prim 从点生长：堆挑最近门外顶点，O(E log V)，稠密图占优，写法与 Dijkstra 同族；
• MST 不等于最短路径树：最小化总边权与最小化各点距离是两个目标，别混用；
• 两个工程坑：不连通图的残缺答案、堆的过期项重复计权，检查动作要写进肌肉记忆。

连通与成本讲完，本章最后一问：图有方向、边即依赖时，怎么排出合法的执行次序——拓扑排序登场。