第四章 图结构心法：遍历、最短路、生成树与拓扑

第四章 · 图结构心法：遍历、最短路、生成树与拓扑

本章要回答的三个问题：树只许有双亲，图放开了所有关系——任意节点可与任意节点相连，结构自由了，麻烦也从哪来？怎么在可能绕圈的网络上系统地走遍每个节点？又怎么在带权、带方向、带依赖的网络里回答"最省、最便宜、次序"这三类问题？

为什么会有这一章

现实世界的关系网几乎全是图：城市间的道路、社交关注、网页超链接、课程先修依赖、任务流水线。图比树多出三样"危险品"——环（走着走着回到原地）、方向（有去无回）、权重（边有代价）。第三章的遍历心法在图上直接失灵：没有 visited 记录，一个三角形就能让递归永远打转。

本章的功课因此按"驯服三样危险品"展开：先解决"怎么表示与走遍"（表示法与 BFS、DFS），再解决"带权网络里离谁最近"（最短路径三式），然后是"连通全网的最便宜骨架"（最小生成树），最后是"方向即依赖时的合法次序"（拓扑排序与强连通分量）。一章下来，图论入门的四梁八柱全部立起。

学图论最容易陷进"算法博物馆"：每个算法都见过、都背过，真拿到一张具体的图却不敢下笔。本章的对策是全程手工演算——Dijkstra 的每轮松弛、Kruskal 的每条选边，都要在纸上走完一遍，走完你才会发现这些算法不过是第二章队列、第三章堆的老朋友换了个战场。

读完能解决什么

对照开头的问题，本章的知识点清单如下：

• 能按"稠密还是稀疏、要否快速查边"在邻接矩阵与邻接表之间选型，并说出两者的空间代价（V 平方对 V 加 E）；
• 能手写 BFS 与 DFS，解释 visited 集合为什么必须存在，并用 BFS 求无权图最短步数；
• 能在给定点数边数时估出两种遍历的复杂度（均为 O(V+E)）；
• 能手工模拟 Dijkstra 的松弛过程表，解释它为何不能处理负权边、Bellman-Ford 为何能、Floyd 何时值得用；
• 能分别用 Prim（从点生长）与 Kruskal（从边生长）求最小生成树，说明 Kruskal 判环为何需要并查集；
• 能用入度法（Kahn）做拓扑排序并检测环路，说出强连通分量的定义与 Tarjan 算法的直觉。

各节怎么分工

先决条件

• 第三章的树遍历（DFS/BFS 是它的推广）与堆（Dijkstra 的引擎）；
• 第二章的队列（BFS 主力）、哈希集合（visited 记录）；
• 第一章的复杂度推导，本章多处要对 V 与 E 分别记账。

往下走到哪

本章出口直接接通三条主线：Kruskal 判环需要的并查集在第七章 7.1 正式修炼；图遍历的骨架（DFS 加剪枝）是第六章回溯法的地基；最短路思想（逐步定型、松弛更新）在第六章动态规划里以"状态转移"的面目重现。工程上，地图导航、任务编排、依赖解析（包管理器）、社交推荐，都在这一章的射程内。

图算法知识全景