程序员数学 05：图、依赖关系与执行顺序

当问题里出现“谁依赖谁”“哪些点可以连通”“怎样走最短”，就可以尝试图模型。图由顶点和边组成，但必须先规定边的方向代表什么。

把任务画成有向图

约定 $A\to B$ 表示 A 完成后 B 才能开始。一个构建任务包含取源码、编译、测试、打包、发布：

查看图表代码

“测试”和“打包”没有相互依赖，允许并行；发布必须等待两者。图只表达约束，不说明资源是否足够、任务是否一定成功，也不保证排程总耗时最优。

用入度推导拓扑排序

入度是指向某顶点的边数。没有未完成前置任务的顶点，入度为 0，可以先处理。

1. 找出所有入度为 0 的顶点。
2. 取出一个，将它加入结果，并移除它指向其他顶点的边。
3. 新出现入度为 0 的顶点继续加入候选队列。
4. 重复直到队列为空。

本例的一种合法顺序是“取源码、编译、测试、打包、发布”，交换测试和打包也合法。如果全部顶点都被处理，就得到了拓扑序；如果还有顶点但没有可处理项，图中存在有向环。

这一结论针对完整的有限依赖图。不能把运行时“没有任务可运行”立即判为环，还需要排除任务失败、外部条件未满足等其他原因。

采用邻接表和高效队列时，每个顶点与每条边处理常数次，总成本为 $O(V+E)$。如果每次都扫描全部顶点找零入度项，实现成本会更高。

环为什么会阻止启动

若又加上“发布后才允许编译”，形成“编译 → 测试 → 发布 → 编译”。这个环内，每个任务都等待另一个任务先完成；线程再多也不能生成第一个满足依赖的任务。

处理方法是检查依赖是否写错，或将初始化与后续处理拆成明确阶段。拓扑排序负责发现不可能的线性执行顺序，不会替你决定业务上应该删哪条边。

不同问题使用不同算法

问题	常用方法	关键前提
是否可达	BFS 或 DFS	明确有向或无向，记录已访问项
无权图最少边数	BFS	每条边成本相同
非负权最短路径	Dijkstra	边权不能为负
依赖执行顺序	拓扑排序	有向无环图才存在完整拓扑序

最少边数不等于最短耗时。如果两条边各耗时 1 秒，另一条直达边耗时 10 秒，按边数选直达路径就不是耗时最短。

练习

1. 依赖为 A→C、B→C、C→D，列出两个合法顺序。
2. 再加 D→A 后，能得到完整拓扑序吗？
3. 路径 A→B→D 的权重是 1、1，A→D 是 5；BFS 的最少边路径是否一定是最小权重路径？

查看答案与讲解

1. A、B、C、D；B、A、C、D。A 和 B 可以互换。
2. 不能，A→C→D→A 形成环。B 可以先处理，不代表剩余任务可完成；必须核对处理顶点数是否等于总数。
3. 不是。BFS 选一条边的 A→D；权重最小的是 A→B→D，总权重 2。

资料与延伸

MIT 6.006 讲义 包含 BFS、DFS、拓扑排序及最短路径。练习画图时，先把“边的方向”和“边权单位”写在纸上，避免模型已经反向而代码仍能运行。