图论算法:三条直觉路线
这一讲不写代码,也不背实现。只回答三个问题: 任务先做谁?一个点到其他点多远?怎样把所有点连通得最便宜? 每个算法都按「直觉 → 规则 → 动画 → 手推」四步走。
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 三步规则
- 把所有入度为 0 的任务放进队列;
- 取出一个任务,输出它;
- 把它所有后继任务的入度减 1;减到 0 就入队。重复到队列空。
如果最后输出的任务数少于总任务数,说明剩下的任务互相卡住,图里有环。
9.2.3 跟着动画走
以 6 个任务的示例手推:入度为 0 的只有 0,先输出 0;
然后 1、2 的入度变成 0,依次输出;最后 3、4、5 依次解锁,得到
0 1 2 3 4 5。
9.2.4 什么时候用,容易错在哪
- 用途:课程安排、任务调度、依赖安装、判断有向图有没有环;
- 拓扑序可能不唯一:同时有多个入度为 0 的点时,先取哪个都可以;
- 如果要求“字典序最小”,每次从候选里取编号最小的即可。
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 出发,手推顺序和最终距离是:
| 轮次 | 选中的点 | 它确定的距离 |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 2 |
| 3 | 2 | 3 |
| 4 | 3 | 3 |
| 5 | 4 | 5 |
| 6 | 6 | 7 |
| 7 | 5 | 8 |
9.3.4 路径怎么还原,为什么不能有负权
更新距离时顺手记下“v 是从哪个 u 过来的”,最后从终点沿着记录倒着走,就能还原整条路径。
如果存在负权边,“已经最近的点的距离”可能以后被一条负边改小, 贪心前提就被破坏,所以 Dijkstra 只适用于非负权图。
9.4 Prim:让一棵树慢慢长大
9.4.1 直觉:从一座城开始“吞并”最近的城
把已经连进来的点看成一个“国家”,树外的点是“邻国”。 每个邻国都记一条“到国家的最便宜道路”; 每轮把最便宜的那个邻国并进来,再更新其他邻国的报价。
9.4.2 跟着动画走
从 0 出发,Prim 的选择顺序和总代价是:
| 轮次 | 新加入的点 | 选中的边 | 边权 |
|---|---|---|---|
| 1 | 1 | 0–1 | 2 |
| 2 | 2 | 1–2 | 2 |
| 3 | 3 | 0–3 | 3 |
| 4 | 4 | 3–4 | 2 |
| 5 | 6 | 2–6 | 4 |
| 6 | 5 | 3–5 | 5 |
| 总权值 | 18 | ||
9.4.3 为什么这样做是对的
当前树内和树外被一条“割”分开,横跨这条割的边里一定有一条必须被选中; 选其中最短的那条不会吃亏——这就是 Prim 的贪心依据。 注意:图必须连通,否则只能得到其中一部分的生成树。
9.5 三问三答
| 问题 | 算法 | 一句话原理 | 结果 |
|---|---|---|---|
| 谁先做? | 拓扑排序 | 反复摘掉入度为 0 的点 | 一个合法顺序;摘不完说明有环 |
| 一个点到各地? | Dijkstra | 每轮锁定最近的点,再松弛邻居 | 源点到所有点的最短距离 |
| 连通最便宜? | Prim | 每次把离当前树最近的邻国并进来 | 总权值最小的生成树 |
记忆时不要背三段实现,记住三个动作:摘零入度、锁定最近、吞并最近。