4.7 设计图而非算法
"将问题建模为图问题后，标准图算法自动解决。" — Steven Skiena, The Algorithm Design Manual
学习目标
- 理解 Skiena 的"设计图而非算法"原则
- 掌握常见问题到图问题的映射
- 明确人机分工：建模是人的工作，执行是机器的工作
- 识别 LLM 在图建模中的常见错误
Skiena 的核心原则
Skiena 在《算法设计手册》中提出一个深刻观点：
"设计图而非算法"
意思是：
- 图算法是一个成熟的算法库：BFS、DFS、拓扑排序、最短路、最大流……
- 一旦你把问题正确地建模为图问题，标准算法会自动解决它
- 真正的难点不是"用 BFS 还是 DFS"，而是"这个问题能建模为图吗"
这个原则直接映射到 LLM 时代的人机分工：
┌─────────────────────────────────────────────────────────────────────┐
│ 人机分工: 建模 vs 实现 │
│ ───────────────────────────────────────────────────────────────── │
│ │
│ 人负责（创造性）: │
│ ├── 识别问题是否可建模为图 │
│ ├── 定义顶点、边、权 │
│ ├── 选择图算法类别（遍历、最短路、流） │
│ └── 判断建模是否正确 │
│ │
│ LLM 负责（机械性）: │
│ ├── 实现标准图算法 │
│ ├── 选择具体算法（BFS/DFS、Dijkstra/BF） │
│ ├── 生成代码 │
│ └── 提供测试用例 │
│ │
│ 人必须判断: │
│ ├── 建模是否遗漏约束 │
│ ├── 算法选择是否匹配问题特性 │
│ └── 边界情况是否覆盖 │
└─────────────────────────────────────────────────────────────────────┘经典映射
调度问题 → 拓扑排序
问题：有 n 门课程，有些课程有先修要求。求一个合法的修课顺序。
图建模：
- 顶点：课程
- 边：A → B 表示"A 是 B 的先修课"
- 问题：求一个拓扑序
算法：拓扑排序（Kahn 或 DFS 逆后序）
注意：如果图有环，说明先修关系矛盾。LLM 实现拓扑排序时容易忽略环检测。
路径规划 → 最短路径
问题：城市之间有道路，求从 A 到 B 的最短路径。
图建模：
- 顶点：城市
- 边：道路（有向或无向）
- 权：距离、时间或费用
- 问题：求最短路径
算法选择：
| 条件 | 算法 |
|---|---|
| 非负权，单源 | Dijkstra |
| 负权可能存在 | Bellman-Ford |
| 全源最短路 | Floyd-Warshall |
常见错误：有权为负时用 Dijkstra。
资源分配 → 网络流
问题：工厂到仓库到零售商，每条运输线有容量限制，求最大运输量。
图建模：
- 顶点：工厂、仓库、零售商
- 边：运输线
- 权：容量
- 问题：求从源点到汇点的最大流
算法：Ford-Fulkerson 或推送-重贴标签
建模细节：
- 源点：虚拟起点，连接所有工厂
- 汇点：虚拟终点，连接所有零售商
- 二部匹配是最大流的特例
连通性问题 → BFS/DFS
问题：社交网络中，判断两个人是否有连接；找出所有的圈子。
图建模：
- 顶点：用户
- 边：好友关系
- 问题：求连通分量
算法：
- BFS/DFS 可以求连通分量
- 并查集适合动态连通性问题
环检测 → DFS
问题：任务调度是否有循环依赖？
图建模：
- 顶点：任务
- 边：A → B 表示"A 必须在 B 之前完成"
- 问题：检测有向图中是否有环
算法：DFS，如果发现后向边则图有环
常见建模错误
错误 1：遗漏约束
场景：物流配送，需要考虑时间窗约束。
错误建模：
- 顶点：配送点
- 边：可达路径
- 权：距离
问题：Dijkstra 只考虑距离，忽略了"某些客户只能在特定时间段收货"的约束。
正确建模：时间窗约束需要建模为时间扩展图（time-expanded graph），或使用约束规划。
错误 2：定义错误
场景：社交网络影响力传播。
错误建模：
- 顶点：用户
- 边：关注关系
- 问题：求影响力最大的 k 个用户
问题：影响力传播不是简单的最短路或最大流。需要使用 Influence Maximization 算法（如 CELF）。
教训：问题名称相似不代表算法相同。
错误 3：算法选择错误
场景：带负权的最短路径。
错误：使用 Dijkstra。
正确：Bellman-Ford 可以处理负权，并检测负权环。
错误 4：环检测遗漏
场景：课程排课。
错误：LLM 实现拓扑排序时，直接返回排序结果，不检测环。
后果：如果课程依赖关系有循环，拓扑排序结果无意义，但程序不报错。
正确：拓扑排序必须包含环检测。
LLM 融合点
任务：让 LLM 建模
给 LLM 一个问题描述，让它建模为图问题。
提示词：
问题描述：某公司有 n 个项目，某些项目有依赖关系（A 必须在 B 之前完成）。
请将这个问题建模为图问题，定义：
1. 顶点是什么
2. 边是什么
3. 边是否有向
4. 问题是求什么你需要判断：
- 建模是否正确？
- 是否遗漏约束？
- 算法选择是否正确？
任务：让 LLM 实现，你审查
给 LLM 一个建模好的图问题，让它实现算法。
提示词：
图结构：
- 顶点：{A, B, C, D, E}
- 边：A→B, A→C, B→D, C→D, D→E
任务：实现拓扑排序。
要求：
1. 包含环检测
2. 如果有环，返回错误
3. 用 Python 实现你需要审查：
- 是否真的包含环检测？
- 环检测逻辑是否正确？
- 边界情况是否处理（空图、单顶点）？
实战练习
练习 1：课程排课
某专业有 8 门必修课，先修关系如下：
- C1 需要先修 C0
- C2 需要先修 C0
- C3 需要先修 C1, C2
- C4 需要先修 C3
- C5 需要先修 C3
- C6 需要先修 C4, C5
- C7 需要先修 C6
任务：
- 将问题建模为图（定义顶点、边）
- 用拓扑排序求合法修课顺序
- 如果加入约束"C5 需要先修 C7"，会发生什么？
练习 2：网络路由
某网络有 6 个路由器，延迟矩阵如下：
R1 R2 R3 R4 R5 R6
R1 0 10 inf 30 inf inf
R2 10 0 20 inf inf inf
R3 inf 20 0 10 20 inf
R4 30 inf 10 0 inf 20
R5 inf inf 20 inf 0 10
R6 inf inf inf 20 10 0任务：
- 将问题建模为图
- 用 Dijkstra 求 R1 到所有路由器的最短路径
- 如果 R3→R4 的延迟变为 -5（奖励链路），还能用 Dijkstra 吗？
练习 3：二部匹配
某公司有 5 个职位和 5 个候选人，候选人的适配情况：
- 候选人 1 适合职位 A, C
- 候选人 2 适合职位 A, B
- 候选人 3 适合职位 B, D
- 候选人 4 适合职位 C, E
- 候选人 5 适合职位 D, E
任务：
- 将问题建模为二部图
- 建模为网络流问题
- 用最大流求最大匹配
小结
"设计图而非算法"原则：
- 问题建模为图问题后，标准算法自动解决
- 建模是创造性的工作，需要人对问题的深刻理解
- LLM 可以实现算法，但不能替代建模判断
人机分工：
| 任务 | 人/LLM | 说明 |
|---|---|---|
| 识别是否为图问题 | 人 | 需要对问题的理解 |
| 定义顶点、边、权 | 人 | 建模核心 |
| 选择算法类别 | 人 | 需要判断问题特性 |
| 判断建模正确性 | 人 | 关键判断点 |
| 实现标准算法 | LLM | 机械性工作 |
| 选择具体算法 | LLM | 在人类确定的类别内选择 |
| 生成代码 | LLM | 翻译工作 |
| 提供测试用例 | LLM | 机械性工作 |
常见错误：遗漏约束、定义错误、算法选择错误、环检测遗漏
参考文献
- Skiena, The Algorithm Design Manual, 3rd ed., Chapter 5
- CLRS, Introduction to Algorithms, 4th ed., Chapters 22-26
- "LLMs+Graphs: Toward Graph-Native, Synergistic AI Systems", arXiv 2026-06