第4章 图算法——建模比算法更重要
本章核心叙事
这章的独特逻辑是：LLM 能做和不能做的边界。问题不是"用 BFS 还是 DFS"，而是"这个问题能建模为图吗"。建模是人的工作，算法实现可以交给 LLM。Skiena 的"设计图而非算法"原则直接映射到人机分工：人负责建模，机器负责执行。
4.1 图的表示与应用
邻接矩阵 vs 邻接表。War Story：获取图本身比算法更重要——数据获取往往是真正的瓶颈。
4.2 BFS 与 DFS
BFS：最短路径（无权）、连通分量、二着色。DFS：环检测、关节点、拓扑排序。
CLRS 的独有贡献：DFS 边分类（树边/后向边/前向边/交叉边）基于发现和完成时间的判定。后向边等价于图有环——这个等价性是图算法形式化的基石。白色/灰色/黑色路径定理。
4.3 拓扑排序与强连通分量
拓扑排序两种方法：Kahn 算法（入度为0的顶点逐步删除）和 DFS 逆后序。Kahn 算法天然检测环——如果存在环则无法删除所有顶点。
强连通分量（SCC）：Kosaraju 算法（两遍 DFS：第一遍逆图后序，第二遍原图按逆后序遍历）和 Tarjan 算法（单遍 DFS + lowlink 值，O(n+m)）。SCC 将有向图压缩为 DAG（condensation），是分析有向图结构的基本工具——网页排名、编译器依赖分析、2-SAT 归约都依赖于 SCC 分解。
4.4 最小生成树
Kruskal（贪心+并查集）和 Prim（贪心+优先队列）。CLRS 给出 MST 切割性质的形式化证明：轻量级边过切割必在某棵 MST 中——Kruskal 和 Prim 都是切割性质的推论。
并查集：按秩合并 + 路径压缩 → O(mα(n))，α(n) ≤ 4 对所有实际 n。这是宇宙中最慢增长的非恒定函数——看似简单的数据结构需要 Ackermann 函数刻画其复杂度。
4.5 最短路径
Dijkstra（非负权）、Bellman-Ford（负权检测）、Floyd-Warshall（全源）、Johnson（稀疏全源）。Bellman-Ford 的形式化正确性证明（路径松弛性质）和 Dijkstra 的归纳正确性证明是 CLRS 独有的。
4.6 最大流
Ford-Fulkerson 方法 + 最大流最小割定理。增广路径的选择影响效率（最短增广路径 O(VE²)）。推送-重贴标签算法维护预流和超额流量，从饱和逐步推进到合法流，无需寻找增广路径——O(V²E)。二部匹配作为最大流的推论。
4.7 设计图而非算法
Skiena 的核心原则：将问题建模为图问题后，标准图算法自动解决。经典映射：调度→拓扑排序、路径规划→最短路径、资源分配→网络流。建模是创造性的，执行是机械的。
4.8 练习
层次一（基础）：
- 证明 DFS 发现后向边当且仅当图有环
- 用切割性质证明 Kruskal 算法的正确性
- 在有向图上运行 Dijkstra，手动追踪优先队列状态
层次二（LLM 协同）： 4. 给出一个建模问题（如课程排课、网络路由），让 LLM 建模为图问题。评价其建模是否正确——建模错误比算法错误更致命 5. 用 LLM 实现拓扑排序，构造让 LLM 忽略环检测的测试用例
层次三（Agent 设计）： 6. 设计 Agent：输入自然语言问题描述，自动识别是否为图问题，选择图算法，生成实现。核心难点是建模而非执行——Agent 的图建模能力是其天花板