第 17 章 图 — 表示、最短路、拓扑、连通与生成树Copy Anchor Link

这一章讲什么: 图(顶点 + 边)怎么存、怎么算:三横三竖的表示选择, 最短路径三算法,Floyd 到 Dijkstra 逐级提速,拓扑排序两版本, 连通性两招,生成树两算法。它在全书链条里的位置: 全书的「综合应用章」——迷宫回溯(第 5 章)、队列/栈遍历(第 10、13 章)、 堆(第 14 章)、并查集思想(第 11 章渐进扩容的亲戚)在此全部会师。

1. 顶层全景Copy Anchor Link

  图 = (顶点, 边);有向/无向;带权/无权
      │
      ├─ 表示:邻接矩阵(查边 O(1)、空间 O(v²)、遍历邻居 O(v))
      │        邻接表(省空间、遍历邻居 O(度)、查边 O(e))
      │        邻接集合(平衡树装邻居:查边 O(log e))
      │
      ├─ 最短路径:
      │    Floyd-Warshall  全源   O(v³)   动态规划(中间点 k 递推)
      │    Bellman-Ford    单源   O(ve)   逐轮松弛,可处理负权
      │    Dijkstra        单源   贪心+堆 不可负权;每次锁最近未访问点
      │
      ├─ 拓扑排序(只对有向无环图 DAG):
      │    Kahn:入度 0 进队列,出队减后继入度;队列空但有剩 = 有环
      │    Tarjan:深搜三色(白/灰/黑),回溯时逆序输出;撞灰 = 有环
      │
      ├─ 连通性:并查集(挂指针成森林,集合数==1 则连通)/ 深搜标visited
      │
      └─ 最小生成树:
           Prim:从一个点长出树,每次拿「离树最近」的点(堆维护距离)
           Kruskal:边从小到大试加,同集合则跳过(并查集判环)

  图说:五个问题 × 每题两三种解法,选型看「有向?带权?单源还是全源?」

2. 主线例子:同一图上的两次算法之旅Copy Anchor Link

用原书的演示图(顶点 A–G,边带权,如 A–B 4、B–A 3、A–E 11、D–A 5…)。

旅程一:Dijkstra 从 A 出发。 初始:A=0、其余 +∞。锁 A: 邻居 B(4)、E(11) 更新;最近未访问是 B(4),锁 B:B 到 A 是 3 但 A 已锁、 B 到 E 是 8 < 11,E 更新为 12(经 B);锁 E…… 每步「锁死最近点、 松弛其出边」,直到目标入锁。要点:一旦锁死不回头,所以负权会骗它 (负权得用 Bellman-Ford)¹。

旅程二:Kruskal 加边。 边按权升序:(C,E) 加、(D,F) 加、(A,B) 加、 (A,D) 加、(B,E) 加——接下来 (D,E) 两端已同集合,会成环,跳过; (E,G) 加,六个顶点五條边,树成²。 对照 Prim:它不从边看,而是从点长——堆里永远装着「每个未选点到已选树 的最短距离」,每次取堆顶。两者同解不同路:Prim 适合稠密图,Kruskal 适合稀疏图。

3. 核心原理Copy Anchor Link

3.1 表示法:时空的交换三件套Copy Anchor Link

邻接矩阵 graph[i][j]:有边存权值(或 true)、无边存 0/+∞;无向图对称。 查边、加删边 O(1);但 v² 空间,邻居少的稀疏图大片浪费, 且「遍历某点所有邻居」要扫整行 O(v)³。 邻接表:每个顶点挂出边列表(书里给的是十字链表式:出边行 + 入边列)。 省空间、遍历邻居快;但「i 和 j 直接相连吗」要 O(e) 扫列表⁴。 邻接集合:邻居用第 11/12 章的平衡树或集合装,查边 O(log e)、 增删 O(log e)、遍历不变——「更复杂的解法」,稠密图或高频查边时用⁵。

3.2 最短路径:从全源到单源逐级提速Copy Anchor Link

Floyd-Warshall:动态规划全场最直接的演示。 定义 d(i,j,k) = 从 i 到 j 只许经过前 k 个顶点的最短路; d(i,j,k) = min(d(i,j,k−1), d(i,k,k−1) + d(k,j,k−1))—— 要么不经过 k,要么把路在 k 处断开。逐层填 v×v 表,O(v³), 一次算出所有点对⁶。

Bellman-Ford:单源。把边列出来,松弛 n−1 轮: 每轮对所有边试「绕行是否更短」。O(ve),比 Floyd 快一档, 且能处理负权(书中用它正是因为 Dijkstra 不能); v−1 轮是「最长简单路径的边数上界」⁷。

Dijkstra:贪心版 Bellman-Ford。每轮锁死当前最近的未访问点 (它的最短距离从此确定——贪心正确性的核心),松弛其出边, 从剩余点里再取最近者。朴素版 O(v²);配第 14 章的堆找最近点, 可到 O(v log v)。负权破坏「锁死不回头」的前提,一票否决¹。

3.3 拓扑排序:排队法与探路法Copy Anchor Link

对有向无环图(DAG)排出一个「边都从前往后」的线性序 (任务调度、依赖构建、课程先修)。两版互为镜像:

• Kahn(队列版):先数每个点的入度;入度 0 的全部入队; 出队输出、其每条出边让目标入度减 1,减到 0 再入队。 结束时若输出不足 n 个,剩下的点互相指着(有环),返回 null⁸。
• Tarjan(深搜三色版):白=未访问、灰=在栈上(递归中)、黑=已完成。 深搜;撞见灰点 = 发现回边 = 有环;一个点递归完染黑、 逆序插入输出(后完成的先输出,unshift 实现)。 「汉塞尔与格雷特式」撒面包屑的比喻出自原书⁹。

3.4 连通与生成树Copy Anchor Link

连通性:并查集版——每个点自成集合,边把两集合并成一个 (新书根挂两旧根),处理完所有边集合数 == 1 即连通; 深搜版——从任意点递归标记,全标到就连通,简单到十几行¹⁰。

最小生成树(MST,第 5 章贪心一节预告过,此处兑现):

• Prim:点生长。堆存 {点, 距已选树的最短距离};反复取堆顶入树、 用它松弛堆里各点的距离。正确性：每次拿的必属某棵 MST(割性质,证明略)¹¹。
• Kruskal:边生长。边升序,并查集判「两端是否已通」,不通则加边并集合。 O(e log e)(排序主导)。D,E 那种「会成环所以跳过」的边, 正是并查集「同集合」的直接判读¹²。

4. 作者的判断与证据Copy Anchor Link

• 表示法选择绑定后续算法:矩阵实现让 Dijkstra 朴素版 O(v²)、 Tarjan 实现 O(v²)(要扫整行找边);「换邻接表可降到 O(ve)」的注 反复出现——表示不是中立的,它给算法定了复杂度底盘¹³。
• 三最短路径算法的适用面有明确口径:全源 Floyd、负权 Bellman-Ford、 非负单源 Dijkstra;「证明略,但可证」在两个贪心算法(Prim/Kruskal)处明说¹²。
• 正确性证明整体缺席(Floyd 递推除外):本章是「会用」而非「会证」的层级。
• 习题含 Floyd 路径回溯、Bellman-Ford 提前终止、Kruskal 自定义排序等增量。

判断(我们的,不是书里的): 本章五个问题共享同一条隐线—— 「松弛」:Floyd 在点集上松弛、Bellman-Ford 在边上松弛、 Dijkstra 在锁点之间松弛、Prim/Kruskal 在生成约束下松弛。 学会认「松弛这一步」,五个算法就从一个背诵清单坍缩成一个动作。 如果错,会错在: 「松弛」统一视角是我们的重构,书中只把它 作为 Bellman-Ford 的术语使用;且 Kruskal 的「跳过成环边」 与其说是松弛不如说是过滤——统一是有代价的简化。

4.1 习题答案的三处增量(「Chapter 17」)Copy Anchor Link

答案文件把正文略过的三块拼上了:

• Floyd 的路径回溯(17.1):再维护一张 next[i][j] 表—— 「站在 i 要去 j,下一步先走到哪」。松弛成功时同步更新 next[i][j] = next[i][k];查路径时从 u 沿 next 一路跳到 v。 O(v³) 不变,多拿全部具体路径¹⁴。
• Bellman-Ford 提前终止(17.2):每轮记 changes,一轮无更新 就 break——实际图上一轮常就收敛,省掉剩余的轮次¹⁵。
• 并查集加速(17.5 + 17.6):正文裸 findParent 的两剂解药都在答案里—— 按大小合并(小树挂大树,合并时维护 size)与路径压缩 (findParent 里顺手 x.ptr = findParent(x.ptr),把沿途节点 直接指向根)。二者合称并查集的标准优化,把近乎 O(n) 的最坏 find 压到近似常数¹⁶。

5. 边界与局限Copy Anchor Link

• A*、 Johnson、 网络流等进阶缺席——「图算法」在此收在经典五问;
• 负环检测只在 Bellman-Ford 语境带过(第 n 轮还能松弛即负环),未展开;
• 邻接表的实现给的是十字链表(出入双链),工程上更常用的是单向出边表 (书中以注释形式承认可用双向链表简化更新);
• 并查集没有讲路径压缩与按秩合并,findParent 是裸递归—— 大图上会退化(补充,不在书里)。

6. 可带走的Copy Anchor Link

1. 三种表示:矩阵(查边 O(1)/空间 v²)、邻接表(省/遍历快/查边 O(e))、 邻接集合(查边 O(log e));表示决定算法的复杂度底盘。
2. Floyd-Warshall:逐中间点松弛,O(v³) 全源,负权 OK。
3. Bellman-Ford:边松弛 n−1 轮,O(ve),负权 OK;可提前终止(某轮无更新即收敛)。
4. Dijkstra:锁最近点 + 堆,O(v log v);负权一票否决。
5. 拓扑排序:Kahn(入度队列)与 Tarjan(三色深搜)互为镜像; 两种都能判环(队列剩点 / 撞灰点)。
6. 连通:并查集(集合数)或深搜标记。
7. MST:Prim(点生长 + 距离堆)与 Kruskal(边排序 + 并查集判环); 稠密用 Prim,稀疏用 Kruskal。
8. 「松弛」是五个算法的共同动作——认出它,图算法就通了。

7. 原文地图Copy Anchor Link