拓扑排序与关键路径：AOV网、拓扑排序算法、AOE网、关键路径计算
各位同学，今天我们来聊一个在工程调度和项目管理中非常实用的算法——拓扑排序与关键路径。说实话，我当年刚接触这部分内容时，觉得它就是个图论的“花架子”，直到有一次在嵌入式系统里做任务调度优化，才真正体会到它的威力。
你想想看，一个大型项目有成百上千个任务，有些任务必须等前置任务完成后才能开始。怎么安排顺序？怎么找出最关键的路径？这就是我们今天要解决的问题。
一、AOV网：用图来描述依赖关系
AOV网（Activity On Vertex network），说白了就是用顶点表示活动，用有向边表示活动之间的先后依赖关系。比如“先穿袜子再穿鞋”，这就是一条从“穿袜子”指向“穿鞋”的边。
我个人习惯把AOV网想象成一个“任务依赖图”。每个节点是一个任务，每条边代表“必须先完成谁”。
核心特征：AOV网中不能有环。如果有环，就意味着任务之间形成了循环依赖，那永远没法开工。
举个例子，一个简单的课程学习依赖关系：
| 课程 | 前置课程 |
|---|---|
| C语言 | 无 |
| 数据结构 | C语言 |
| 算法分析 | 数据结构 |
| 操作系统 | C语言, 数据结构 |
这个关系画成AOV网，就是一条从“C语言”出发，指向“数据结构”，再指向“算法分析”的路径，同时“C语言”和“数据结构”都指向“操作系统”。
二、拓扑排序算法：找出合理的执行顺序
拓扑排序，就是给AOV网中的顶点排个序，使得对于每一条有向边(u, v)，u在排序中都出现在v之前。说白了，就是找出一个“不违反任何依赖”的任务执行顺序。
算法其实很简单，我常用的方法是Kahn算法：
- 统计每个顶点的入度（有多少条边指向它）
- 把所有入度为0的顶点入队
- 从队列中取出一个顶点，输出它，然后把它所有出边的终点入度减1
- 如果某个终点的入度变成0，就把它入队
- 重复直到队列为空
注意：如果最后输出的顶点数少于总顶点数，说明图中存在环。我曾经在一个项目里调试了半天，最后发现是需求文档里有个循环依赖没被发现——拓扑排序直接帮我抓出了这个bug。
代码实现也很直接：
#define MAXV 100
typedef struct {
int edges[MAXV][MAXV];
int n; // 顶点数
} Graph;
void topologicalSort(Graph* g) {
int indegree[MAXV] = {0};
int queue[MAXV], front = 0, rear = 0;
int count = 0;
// 计算入度
for (int i = 0; i < g->n; i++)
for (int j = 0; j < g->n; j++)
if (g->edges[i][j])
indegree[j]++;
// 入度为0的顶点入队
for (int i = 0; i < g->n; i++)
if (indegree[i] == 0)
queue[rear++] = i;
while (front < rear) {
int v = queue[front++];
printf("%d ", v);
count++;
for (int j = 0; j < g->n; j++) {
if (g->edges[v][j]) {
indegree[j]--;
if (indegree[j] == 0)
queue[rear++] = j;
}
}
}
if (count != g->n)
printf("\n图中存在环！");
}嗯，这里要注意：队列的实现可以用数组模拟，也可以用链表。我个人习惯用数组，因为嵌入式环境下动态分配内存有时不太方便。
三、AOE网：给活动加上时间
AOE网（Activity On Edge network）和AOV网不同，它用边表示活动，用顶点表示事件。每条边上有权重，代表活动所需的时间。
你想想看，AOE网解决的是另一个问题：给定每个活动的耗时，整个项目最早什么时候能完成？哪些活动是“关键”的，一旦延误就会拖累整个项目？
关键概念：
- 事件的最早发生时间（ve）：从起点到该顶点的最长路径长度
- 事件的最迟发生时间（vl）：在不延误整个工期的前提下，该事件最晚必须发生的时间
- 活动的最早开始时间（e）：等于起点事件的最早发生时间
- 活动的最迟开始时间（l）：等于终点事件的最迟发生时间减去活动耗时
关键路径，就是那些e等于l的活动组成的路径。说白了，这些活动一点都不能拖延。
四、关键路径计算：一步一步来
计算关键路径分四步走：
- 对AOE网进行拓扑排序，得到拓扑序列
- 按拓扑顺序计算每个事件的最早发生时间ve
- 按逆拓扑顺序计算每个事件的最迟发生时间vl
- 根据ve和vl计算每个活动的最早/最迟开始时间，找出关键活动
我曾经在一个嵌入式项目的开发计划中用过这个方法。当时项目经理拍脑袋定了3个月的工期，我用关键路径一算，发现最短也要3个半月。后来跟老板沟通，要么加人，要么砍需求——这就是关键路径的价值，它让你知道“底线在哪里”。
计算ve的公式很简单：
ve[j] = max(ve[i] + weight(i, j)) 对所有以j为终点的边计算vl的公式：
vl[i] = min(vl[j] - weight(i, j)) 对所有以i为起点的边下面是一个完整的计算示例：
// 假设有6个事件，8个活动
// 拓扑序列: 0, 1, 2, 3, 4, 5
// 第一步：计算ve
ve[0] = 0;
ve[1] = ve[0] + 6 = 6;
ve[2] = max(ve[0] + 4, ve[1] + 1) = max(4, 7) = 7;
ve[3] = ve[1] + 5 = 11;
ve[4] = max(ve[2] + 2, ve[3] + 3) = max(9, 14) = 14;
ve[5] = max(ve[3] + 4, ve[4] + 1) = max(15, 15) = 15;
// 第二步：计算vl
vl[5] = ve[5] = 15;
vl[4] = vl[5] - 1 = 14;
vl[3] = min(vl[4] - 3, vl[5] - 4) = min(11, 11) = 11;
vl[2] = vl[4] - 2 = 12;
vl[1] = min(vl[2] - 1, vl[3] - 5) = min(11, 6) = 6;
vl[0] = min(vl[1] - 6, vl[2] - 4) = min(0, 8) = 0;
// 第三步：计算每个活动的e和l
// 活动(0,1): e=0, l=vl[1]-6=0, 关键活动
// 活动(0,2): e=0, l=vl[2]-4=8, 非关键
// 活动(1,2): e=6, l=vl[2]-1=11, 非关键
// 活动(1,3): e=6, l=vl[3]-5=6, 关键活动
// 活动(2,4): e=7, l=vl[4]-2=12, 非关键
// 活动(3,4): e=11, l=vl[4]-3=11, 关键活动
// 活动(3,5): e=11, l=vl[5]-4=11, 关键活动
// 活动(4,5): e=14, l=vl[5]-1=14, 关键活动
// 关键路径: 0 -> 1 -> 3 -> 4 -> 5
// 总工期: 15避坑指南：我曾经犯过一个错误——直接用ve和vl的差值来判断关键活动。其实应该用活动的e和l来比较。ve和vl是针对事件的，e和l才是针对活动的。这两个概念别搞混了。
下面我用一张图来总结整个知识体系：
这张图把整个知识脉络串起来了：从AOV网出发，通过拓扑排序得到执行顺序，再到AOE网引入时间维度，最后用关键路径找出最紧要的活动。每一步都是下一步的基础。
实用建议：在实际项目中，我通常先用拓扑排序检查依赖关系有没有环，然后再用关键路径分析工期。这两个工具配合使用，能帮你把项目计划做得更扎实。
好了，拓扑排序和关键路径的核心内容就这些。记住：拓扑排序解决“能不能做”的问题，关键路径解决“多久做完”的问题。两者结合，就是一套完整的项目调度分析工具。
公众号:蓝海资料掘金营，微信deep3321