第18章拓扑排序与关键路径

课程目录第18章拓扑排序与关键路径

18. 拓扑排序与关键路径：从依赖关系到项目工期

图论里有两类问题，我做了这么多年嵌入式系统，几乎每个项目都会碰到。一类是拓扑排序，解决的是「谁先谁后」的问题；另一类是关键路径，解决的是「整个项目最短要多久」的问题。

说白了，拓扑排序管的是依赖关系，关键路径管的是时间底线。你想想看，一个大型软件项目，几十个模块，哪个先编译、哪个后链接，这就是拓扑排序。而整个项目从启动到交付，哪条路径上的任务一天都不能拖，这就是关键路径。

好，我们一个一个来拆。

18.1 AOV网与拓扑排序（Kahn算法）

AOV网（Activity On Vertex network）是用顶点表示活动、用有向边表示活动之间的先后关系。比如课程学习中，数据结构必须在算法设计之前学完，这就是一条有向边。

拓扑排序，就是把AOV网中的所有顶点排成一个线性序列，使得如果存在一条从u到v的边，那么u在序列中一定出现在v之前。

我个人习惯用Kahn算法来实现拓扑排序。它的核心思想很简单：

统计每个顶点的入度（有多少条边指向它）
把所有入度为0的顶点入队
出队一个顶点，把它所有邻接顶点的入度减1
如果某个邻接顶点入度变成0，就入队
重复直到队列为空

如果最后输出的顶点数不等于总顶点数，说明图中存在环——这在项目中意味着有循环依赖，是个大坑。

  核心要点：拓扑排序的结果不唯一。只要满足依赖关系，任何顺序都是合法的。

来看代码实现：

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

#define MAX_VERTICES 100

// 邻接表节点
typedef struct EdgeNode {
    int adjvex;
    struct EdgeNode *next;
} EdgeNode;

// 顶点节点
typedef struct VertexNode {
    int data;
    int in;  // 入度
    EdgeNode *firstedge;
} VertexNode, AdjList[MAX_VERTICES];

typedef struct {
    AdjList adjList;
    int numVertexes, numEdges;
} GraphAdjList;

// Kahn算法实现拓扑排序
int TopologicalSort(GraphAdjList *G) {
    int *stack = (int *)malloc(G->numVertexes * sizeof(int));
    int top = 0;  // 栈顶指针
    int count = 0;  // 已输出顶点数
    
    // 将所有入度为0的顶点入栈
    for (int i = 0; i < G->numVertexes; i++) {
        if (G->adjList[i].in == 0) {
            stack[top++] = i;
        }
    }
    
    while (top != 0) {
        int gettop = stack[--top];
        printf("%d -> ", G->adjList[gettop].data);
        count++;
        
        // 遍历该顶点的邻接表
        for (EdgeNode *e = G->adjList[gettop].firstedge; e; e = e->next) {
            int k = e->adjvex;
            // 邻接顶点入度减1
            if (--G->adjList[k].in == 0) {
                stack[top++] = k;
            }
        }
    }
    
    free(stack);
    
    if (count < G->numVertexes) {
        printf("\n图中存在环！拓扑排序失败。\n");
        return 0;
    }
    printf("\n拓扑排序完成。\n");
    return 1;
}

我的经验：我在做嵌入式系统的任务调度器时，就用过这个算法。当时有个模块依赖关系配错了，形成了循环依赖，系统一启动就死锁。用Kahn算法一跑，立马抓出了那个环。嗯，从那以后，我每次做依赖配置都会先用拓扑排序验证一遍。

18.2 AOE网与关键路径

AOE网（Activity On Edge network）是用顶点表示事件、用边表示活动、边的权值表示活动持续时间。它通常用来估算整个项目的最短工期。

关键路径，就是AOE网中从源点到汇点路径长度最长的那条路径。为什么最长反而关键？因为这条路径上的任何一个活动延误了，整个项目就得延期。说白了，它就是项目的「瓶颈」。

计算关键路径需要四个参数：

事件最早发生时间（ve）：从源点出发，到达该事件的最早时间
事件最晚发生时间（vl）：在不延误整个工期的前提下，该事件必须发生的最晚时间
活动最早开始时间（ee）：活动对应的起点事件的最早发生时间
活动最晚开始时间（el）：活动对应的终点事件的最晚发生时间减去活动持续时间

当 ee == el 时，这个活动就是关键活动。所有关键活动连起来，就是关键路径。

注意：关键路径可能不止一条。多条关键路径意味着项目更脆弱——任何一条关键路径上的延误都会影响总工期。

计算步骤分两趟：

正向计算ve：按拓扑顺序，ve[j] = max(ve[i] + weight(i,j))
反向计算vl：按逆拓扑顺序，vl[i] = min(vl[j] - weight(i,j))

我曾经在一个嵌入式固件开发项目中吃过亏。当时项目经理拍脑袋说「这个模块3天能搞定」，结果那个模块正好在关键路径上，一拖就是一周，整个项目延期。后来我专门画了AOE网，把关键路径标出来，谁都不敢再乱估工期了。

18.3 事件与活动的最早/最晚时间

我们来细化一下这四个时间的计算方法。假设我们有一个AOE网，顶点编号0到n-1，0是源点，n-1是汇点。

事件最早发生时间 ve：

ve[0] = 0
ve[j] = max{ ve[i] + weight(i,j) }，其中i是j的所有前驱

事件最晚发生时间 vl：

vl[n-1] = ve[n-1]
vl[i] = min{ vl[j] - weight(i,j) }，其中j是i的所有后继

活动最早开始时间 ee：

ee(i,j) = ve[i]

活动最晚开始时间 el：

el(i,j) = vl[j] - weight(i,j)

来看一个完整的计算示例表格：

活动	起点→终点	持续时间	ee	el	el - ee	是否关键
a1	0→1	6	0	0	0	✓
a2	0→2	4	0	2	2
a3	0→3	5	0	3	3
a4	1→4	1	6	6	0	✓
a5	2→4	1	4	6	2
a6	3→5	2	5	8	3
a7	4→6	9	7	7	0	✓
a8	5→6	4	7	11	4

从表中可以看出，关键活动是a1、a4、a7，它们构成了一条关键路径：0→1→4→6，总工期为6+1+9=16。

避坑指南：我曾经在计算vl时犯过一个低级错误——直接用ve[n-1]作为所有vl的初始值，然后正向遍历。这是错的！vl必须按逆拓扑顺序计算，否则结果全乱套。你想想看，后面的时间还没算出来，前面的怎么可能算得对？

18.4 知识体系总览

下面这张图把本章的核心逻辑串起来了，建议你多看几遍：

这张图把AOV网和AOE网的关系、四个时间参数的计算、以及关键路径的判定都串起来了。你把它打印出来贴在工位上，做项目排期的时候瞄一眼，思路会清晰很多。

  总结一句话：拓扑排序解决「能不能做」的问题，关键路径解决「多久能做完」的问题。两者结合，就是一套完整的项目依赖与工期分析工具。

好了，这一章的内容就到这里。代码和思路都给你了，剩下的就是多练。下次遇到项目排期，试着画一张AOE网，算一算关键路径——你会发现，很多「我以为很快」的任务，其实都在关键路径上等着你呢。

📚 课程目录

18. 拓扑排序与关键路径：从依赖关系到项目工期

18.1 AOV网与拓扑排序（Kahn算法）

18.2 AOE网与关键路径

18.3 事件与活动的最早/最晚时间

18.4 知识体系总览