22. 拓扑排序与关键路径：AOV网与拓扑排序、AOE网与关键路径

图论里有两个非常实用的工具——拓扑排序和关键路径。说实话，我在做编译器优化和项目排期时，几乎天天跟它们打交道。你想想看，一个工程有几十个任务，哪个先做哪个后做？整个工期最短要多久？这些问题，靠直觉是搞不定的。

这一章，我们就来拆解这两个概念。我会结合我踩过的坑，帮你把原理和代码都吃透。

22.1 AOV网与拓扑排序

AOV网（Activity On Vertex），说白了就是用顶点表示活动，用有向边表示活动之间的先后依赖关系。比如“先修完C语言，才能学数据结构”，这就是一条有向边。

拓扑排序，就是给AOV网里的所有顶点排个序。规则很简单：如果A必须在B之前完成，那么排序结果里A一定在B前面。

嗯，这里要注意：如果图里有环，拓扑排序就做不了。为什么？因为环意味着循环依赖——A等B，B等C，C又等A，这活没法干。我在项目中遇到过一回，需求文档里有个隐藏的循环依赖，排期排了三天才发现，气得我直接重构了依赖图。

22.1.1 拓扑排序的两种实现

我个人习惯用Kahn算法（基于入度），因为它直观，而且能顺便检测环。思路是这样的：

1. 统计每个顶点的入度（有多少条边指向它）。
2. 把所有入度为0的顶点入队（这些顶点没有前置依赖，可以马上执行）。
3. 弹出队首顶点，把它加入结果列表。然后“删除”它发出的所有边——也就是把它的邻居的入度减1。如果某个邻居入度变成0了，就入队。
4. 重复，直到队列为空。

如果最后结果列表里的顶点数不等于总顶点数，说明图里有环。

来看代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// 邻接表节点
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 图结构
typedef struct {
    Node* adjList[MAX_VERTICES];
    int inDegree[MAX_VERTICES];
    int numVertices;
} Graph;

// 初始化图
void initGraph(Graph* g, int n) {
    g->numVertices = n;
    for (int i = 0; i < n; i++) {
        g->adjList[i] = NULL;
        g->inDegree[i] = 0;
    }
}

// 添加有向边 u -> v
void addEdge(Graph* g, int u, int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = g->adjList[u];
    g->adjList[u] = newNode;
    g->inDegree[v]++;
}

// Kahn算法拓扑排序
int topologicalSort(Graph* g, int result[]) {
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;
    int idx = 0;

    // 所有入度为0的顶点入队
    for (int i = 0; i < g->numVertices; i++) {
        if (g->inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }

    while (front < rear) {
        int u = queue[front++];
        result[idx++] = u;

        Node* p = g->adjList[u];
        while (p) {
            int v = p->vertex;
            g->inDegree[v]--;
            if (g->inDegree[v] == 0) {
                queue[rear++] = v;
            }
            p = p->next;
        }
    }

    // 如果结果数量不等于顶点数，说明有环
    return (idx == g->numVertices);
}

int main() {
    Graph g;
    initGraph(&g, 6);
    addEdge(&g, 5, 2);
    addEdge(&g, 5, 0);
    addEdge(&g, 4, 0);
    addEdge(&g, 4, 1);
    addEdge(&g, 2, 3);
    addEdge(&g, 3, 1);

    int result[6];
    if (topologicalSort(&g, result)) {
        printf("拓扑排序结果: ");
        for (int i = 0; i < 6; i++) {
            printf("%d ", result[i]);
        }
        printf("\n");
    } else {
        printf("图中存在环，无法拓扑排序\n");
    }
    return 0;
}

22.1.2 拓扑排序的应用场景

除了课程安排，我还在这些地方用过：

• 编译器的依赖分析：源文件之间的#include关系，必须按拓扑顺序编译。
• 任务调度系统：比如Spark的DAG调度器，就是基于拓扑排序来决定执行顺序。
• Makefile构建：make工具会分析目标文件之间的依赖，然后拓扑排序后执行。

22.2 AOE网与关键路径

AOE网（Activity On Edge），用边表示活动，用顶点表示事件。边的权重就是活动耗时。AOE网通常用来算整个工程的最短工期，以及哪些活动是“关键”的——一旦延误，整个项目就延期。

关键路径，就是AOE网中从源点到汇点最长的路径。为什么是最长？因为整个项目的工期取决于最慢的那条链路。你想想看，一个项目里，有的活动可以慢慢来，但关键路径上的活动一天都不能拖。

22.2.1 关键路径的四个关键量

要找出关键路径，我们需要算四个值。我个人习惯把它们记成“最早”和“最晚”两组：

符号	含义	怎么算
ve(v)	事件v的最早发生时间	从源点开始，按拓扑顺序递推：ve(v) = max(ve(u) + w(u,v))
vl(v)	事件v的最晚发生时间	从汇点开始，按逆拓扑顺序递推：vl(v) = min(vl(u) - w(v,u))
e(e)	活动e的最早开始时间	等于活动起点事件的最早发生时间：e(e) = ve(u)
l(e)	活动e的最晚开始时间	等于活动终点事件的最晚发生时间减去活动耗时：l(e) = vl(v) - w(u,v)

如果某个活动的 e(e) == l(e)，也就是说最早开始时间和最晚开始时间相等，那它就是关键活动。所有关键活动连起来，就是关键路径。

22.2.2 关键路径的计算步骤

我一般分三步走：

1. 拓扑排序：得到顶点的拓扑序列。
2. 正向递推：按拓扑顺序计算每个事件的最早发生时间 ve。
3. 反向递推：按逆拓扑顺序计算每个事件的最晚发生时间 vl。
4. 判断关键活动：对每条边，算 e 和 l，相等就是关键活动。

来看一个具体的例子。假设有这样一个AOE网：

顶点：0(源点), 1, 2, 3, 4(汇点)
边：
0->1 耗时6
0->2 耗时4
1->3 耗时1
2->3 耗时1
3->4 耗时2

计算过程：

• ve(0)=0, ve(1)=6, ve(2)=4, ve(3)=max(6+1, 4+1)=7, ve(4)=7+2=9
• vl(4)=9, vl(3)=9-2=7, vl(1)=7-1=6, vl(2)=7-1=6, vl(0)=min(6-6, 6-4)=0
• 活动0->1: e=0, l=6-6=0 → 关键活动
• 活动0->2: e=0, l=6-4=2 → 非关键
• 活动1->3: e=6, l=7-1=6 → 关键活动
• 活动2->3: e=4, l=7-1=6 → 非关键
• 活动3->4: e=7, l=9-2=7 → 关键活动

所以关键路径是：0 → 1 → 3 → 4，总工期9天。

22.3 知识体系总览

下面这张图，把AOV网、AOE网、拓扑排序和关键路径的关系梳理清楚了。我建议你多看几遍，理解它们之间的逻辑链条。

22.4 总结与避坑

拓扑排序和关键路径，说白了就是把复杂的依赖关系理清楚，然后找出最要命的那条线。我个人觉得，这两个算法是图论里最“实用”的——你几乎在任何涉及流程、工期、依赖的系统里都能用到它们。

最后给你几个我总结的避坑指南：

• 拓扑排序前一定要先检测环。我曾经在项目里直接跑排序，结果死循环了，排查了半天才发现是依赖图有环。
• 关键路径可能不止一条。如果有多条路径的总耗时相同且都是最大，那它们都是关键路径。每条路径上的活动都不能延误。
• AOE网中只能有一个源点和一个汇点。如果有多个，可以加一个虚拟源点/汇点，用0权边连接。
• 代码实现时注意浮点数精度。如果活动耗时是小数，比较 e==l 时要用容差，比如 fabs(e-l) < 1e-6。

好了，这一章的内容就到这里。拓扑排序和关键路径，你学会了吗？

---