Prim 最小生成树算法

带权无向图的一棵生成树包含全部顶点，并且连通、无环。最小生成树是在这些树中边权总和最小的一棵，含有 $n-1$ 条边。只有连通图才有生成树。

边权可以是负数。最小生成树与“权值最小的连通子图”并不总是同一个问题：负权环可能值得全部保留，但树不允许有环。

割性质

把顶点分成非空的两部分，连接两部分的边称为跨割边。若已经选出的边都不跨这个割，则一条最小权跨割边可以安全加入：存在一棵包含已有边和这条边的最小生成树。

证明采用交换。取一棵包含已有边的最小生成树，加入该跨割边后形成环。环上必有另一条跨割边，且它不属于已有边。删去这条不更轻的边后仍是一棵生成树，总权值没有增加。

Prim 的选择规则

维护已加入生成树的顶点集合 $S$，每次选择连接 $S$ 和其余顶点的最小权边。已有树边都在 $S$ 内部，因此每次选择都满足割性质。

best[v] 表示从 $S$ 连到 $v$ 的最小单边权值，不是从起点到 $v$ 的路径长度。

实现

邻接表存储 (邻居, 权值)，每条无向边需要双向存储。返回总权值和树边；非连通图返回 None。

from heapq import heappop, heappush
from math import inf

def prim(adj):
    n = len(adj)
    if n == 0:
        return 0, []
    best = [inf] * n
    used = [False] * n
    best[0] = 0
    heap = [(0, 0, -1)]
    total, tree = 0, []
    while heap:
        weight, u, parent = heappop(heap)
        if used[u]:
            continue
        used[u] = True
        total += weight
        if parent != -1:
            tree.append((parent, u, weight))
        for v, cost in adj[u]:
            if not used[v] and cost < best[v]:
                best[v] = cost
                heappush(heap, (cost, v, u))
    return (total, tree) if all(used) else None

懒删除堆最多保存 $O(m)$ 个条目，时间为 $O(n+m\log(m+1))$；简单连通图上通常写作 $O(m\log n)$。朴素版本每次扫描所有未加入顶点，时间为 $O(n^2+m)$。

例题

• 洛谷 P3366 最小生成树