专题进阶 · 图算法推荐总顺序 · 第 80 / 148 课

维护一棵已连接的树,每次选择跨出边界的最轻边,并跳过过期候选。

先学会这些,再进入本课 最小生成树 优先队列
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

PrimPrim

从一个节点生长树,每次选择跨越树与外部的最轻边。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

维护一棵已连接的树,每次选择跨出边界的最轻边,并跳过过期候选。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

从一个城市开始逐步铺网,怎样只考虑当前已联网区域与外界之间的边?

02一步步得到方法

与 Kruskal 的森林视角对照

Prim 始终生长一棵树。起点加入后,把连接外部节点的边放入小根堆,每次取最轻跨边,将新节点加入树,再把它的出边加入候选。

边堆里会残留终点已经在树内的记录。这些边此时不再跨越割,必须跳过;不能因为是堆顶最轻就盲目接受。

为什么不需要累计源点距离

优先级是单条跨边的权重 w,而不是 dist[u]+w。Prim 最小化总铺网成本,Dijkstra 最小化源点路径代价;两者都用堆,却维护不同不变量。

当前树节点与其余节点构成一个割,选择其最轻跨边由割性质保证安全。图不连通时,堆会提前耗尽,无法覆盖所有节点。

每次选择当前树与外部之间的边

Prim 维护一个已经连通的节点集合,只从跨出这个集合的边中选最小边。它与 Kruskal 全图按边排序不同,也与 Dijkstra 选择最小累计距离不同。

惰性堆可能含两端都已进入树的旧边,出堆时要跳过。若误用从起点的累计距离作为键,就会把目标悄悄改成最短路径树。

03把一个小例子完全算清楚

边 0–1:2、0–2:3、1–2:1、2–3:4,从 0 出发。

步骤计算与状态为什么这样做
树 {0}候选 0–1:2、0–2:3选权重 2
树 {0,1}新增 1–2:1选 1,而非按源点累计 3 比较
树 {0,1,2}旧 0–2:3 已过期跳过
加入 3选 2–3:4,总重 7完成

窄屏可左右滑动表格,阅读完整计算与理由。

跨边代价与路径代价必须分开理解。

04为什么这个方法成立

  1. 已接受边始终连接一个新节点,因此维持树且无环。
  2. 堆中保留所有从已选树通向外部的候选边。
  3. 跳过内部边后弹出的最轻边就是最轻跨割边,逐轮安全。

05把推导翻译成代码

Python · 可独立运行的教学实现

import heapq
def prim(n, edges):
    if n == 0:
        return 0
    adj = [[] for _ in range(n)]
    for u,v,w in edges:
        adj[u].append((w,v)); adj[v].append((w,u))
    heap, seen, total = [(0,0)], set(), 0
    while heap:
        weight,u = heapq.heappop(heap)
        if u in seen:
            continue
        seen.add(u); total += weight
        for w,v in adj[u]:
            if v not in seen:
                heapq.heappush(heap,(w,v))
    return total if len(seen)==n else None

逐个理解关键决定

[(0,0)]
起点用虚拟零成本入口,后续真实边权才累入成本。
(w,v)
键是边权,不是 total+w 或源点路径长度。

06时间、空间与实现范围

本惰性边堆版本 O(E log(E+1)+V),堆最坏 O(E),邻接表 O(V+E)。

稠密图可用 O(V²) 扫描版,带索引的堆版也有不同复杂度;应对应实际实现。

07改变条件,检查哪里会出错

发现节点时立刻 seen

可能在更便宜跨边出现前锁定它;本版本在最轻候选弹出时接纳。

只运行一次就覆盖断开的图

从一个起点只能扩展其连通分量;要返回森林需遍历其他未访问起点。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

允许负权吗?

需要一点提示

割性质是否要求非负?

查看解析与答案

允许;虚拟起点为 0 不限制后续负边加入。

练习 2 · 边界与辨析

Prim 从不同起点开始总重会变吗?

需要一点提示

最小树是否唯一?

查看解析与答案

在连通图上最优总重相同,等权时选出的边集可以不同。

练习 3 · 变式与迁移

不连通图怎样扩展为森林?

需要一点提示

为未访问分量重新启动。

查看解析与答案

外层遍历所有未访问节点,每个分量独立运行 Prim,分别记录生成树。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。