第 09 讲

图论算法:三条直觉路线

这一讲不写代码,也不背实现。只回答三个问题: 任务先做谁?一个点到其他点多远?怎样把所有点连通得最便宜? 每个算法都按「直觉 → 规则 → 动画 → 手推」四步走。

预计 80 分钟 前置:第 08 讲图的术语与存储结构 关键词:入度 · 松弛 · 贪心长树

9.1 先看懂三个问题

9.1.1 三个问题,三种答案

① 谁先做?

任务之间有先后依赖,要排一个合法顺序。
拓扑排序

② 从这里到各地多远?

给定一个起点,求它到其他所有点的最短距离。
Dijkstra 单源最短路

③ 怎样连通最便宜?

用最少的总修路代价,把所有城市连成一张网。
Prim 最小生成树

9.1.2 两张演示图

任务图用来讲拓扑排序:顶点是任务,箭头表示“必须先后”。 例如 0→1 表示任务 0 完成之前不能做任务 1。

地图用来讲后面两个算法:7 个城市、11 条带权道路,边权可以理解成公里数或运费。 它既有“直连很贵、绕路更便宜”的情况,也有“多条路都能连通”的选择。

这一讲的看法 每个算法都先问“如果让我手工做,我会怎么做”,再把手工动作翻译成规则; 最后用动画逐步验证。不要一上来记步骤。

9.2 拓扑排序:先做没有前置的任务

9.2.1 直觉:入度就是“还有几个前置”

一个任务的入度,就是有多少个任务必须排在它前面。 入度为 0,说明它现在就可以做;做完它,就把它从别人的“前置清单”里划掉。

9.2.2 三步规则

  1. 把所有入度为 0 的任务放进队列;
  2. 取出一个任务,输出它;
  3. 把它所有后继任务的入度减 1;减到 0 就入队。重复到队列空。

如果最后输出的任务数少于总任务数,说明剩下的任务互相卡住,图里有环。

9.2.3 跟着动画走

动画怎么看 橙色 = 当前队列里“可以做”的任务;绿色 = 已经输出; 每输出一个点,注意它的后继入度怎么减。

以 6 个任务的示例手推:入度为 0 的只有 0,先输出 0; 然后 1、2 的入度变成 0,依次输出;最后 3、4、5 依次解锁,得到 0 1 2 3 4 5。

9.2.4 什么时候用,容易错在哪

9.3 Dijkstra:从近到远,一个一个确定

9.3.1 直觉:先确定最近的点

把起点到各点的距离写在点上。每轮挑当前距离最小、还没确定的点, 把它标记为“最终答案”,再用它去更新邻居。 因为边权非负,最近的点不可能再被更远的点“绕回来”改小。

9.3.2 唯一的核心动作:松弛

如果已经知道到 u 的最短距离,而从 u 到 v 有一条权为 w 的边, 那么“先到 u,再走这条边”的候选距离就是 dist[u] + w。 如果它比现在的 dist[v] 小,就更新 dist[v]。

9.3.3 跟着动画走

动画怎么看 每轮先看“谁被选中”,橙色表示这一轮被更新的点和边; 被选中的点会变成“已确定”,之后不再改。

从 0 出发,手推顺序和最终距离是:

轮次选中的点它确定的距离
100
212
323
433
545
667
758

9.3.4 路径怎么还原,为什么不能有负权

更新距离时顺手记下“v 是从哪个 u 过来的”,最后从终点沿着记录倒着走,就能还原整条路径。

如果存在负权边,“已经最近的点的距离”可能以后被一条负边改小, 贪心前提就被破坏,所以 Dijkstra 只适用于非负权图。

9.4 Prim:让一棵树慢慢长大

9.4.1 直觉:从一座城开始“吞并”最近的城

把已经连进来的点看成一个“国家”,树外的点是“邻国”。 每个邻国都记一条“到国家的最便宜道路”; 每轮把最便宜的那个邻国并进来,再更新其他邻国的报价。

9.4.2 跟着动画走

动画怎么看 绿色 = 已经进树的点和边;橙色 = 当前最便宜的候选边。 每轮只加一个点、一条边,加到 n−1 条边就停。

从 0 出发,Prim 的选择顺序和总代价是:

轮次新加入的点选中的边边权
110–12
221–22
330–33
443–42
562–64
653–55
总权值18

9.4.3 为什么这样做是对的

当前树内和树外被一条“割”分开,横跨这条割的边里一定有一条必须被选中; 选其中最短的那条不会吃亏——这就是 Prim 的贪心依据。 注意:图必须连通,否则只能得到其中一部分的生成树。

9.5 三问三答

问题算法一句话原理结果
谁先做?拓扑排序反复摘掉入度为 0 的点一个合法顺序;摘不完说明有环
一个点到各地?Dijkstra每轮锁定最近的点,再松弛邻居源点到所有点的最短距离
连通最便宜?Prim每次把离当前树最近的邻国并进来总权值最小的生成树

记忆时不要背三段实现,记住三个动作:摘零入度、锁定最近、吞并最近。