第18讲：图的拓扑排序与关键路径

图论里有两个非常实用的概念——拓扑排序和关键路径。说实话，我刚入行时觉得这俩就是考试题，直到有一次做项目排期，才真正体会到它们的价值。今天咱们就把这两个东西彻底讲透。

一、AOV网与拓扑排序

先说说AOV网。AOV是Activity On Vertex的缩写，也就是用顶点表示活动，用有向边表示活动之间的先后关系。比如你要做一道菜，得先洗菜再切菜，最后才能炒菜。这个依赖关系，用AOV网表示就非常清晰。

拓扑排序，就是把AOV网中的所有顶点排成一个线性序列，使得如果存在从A到B的有向边，那么A在序列中一定出现在B之前。说白了，就是给一堆有依赖关系的活动排个序，让它们能顺利执行下去。

我当年在做一个编译器的依赖分析模块时，就遇到过这种情况。多个源文件之间有include依赖，必须按拓扑顺序编译，否则就会报错。嗯，那时候我才真正理解了拓扑排序的实用价值。

拓扑排序算法

算法其实不复杂，核心思路是：每次找一个入度为0的顶点（也就是没有前置依赖的活动），把它输出，然后删除它发出的所有边。重复这个过程，直到所有顶点都被输出。

// 拓扑排序 - 基于邻接表
#define MAX_VERTEX 100

typedef struct EdgeNode {
    int adjvex;
    struct EdgeNode *next;
} EdgeNode;

typedef struct VertexNode {
    int data;
    int indegree;  // 入度
    EdgeNode *firstedge;
} VertexNode, AdjList[MAX_VERTEX];

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

// 拓扑排序
int TopologicalSort(GraphAdjList *G) {
    int stack[MAX_VERTEX];  // 用数组模拟栈
    int top = -1;
    int count = 0;  // 统计输出的顶点数
    
    // 先把所有入度为0的顶点入栈
    for (int i = 0; i < G->numVertexes; i++) {
        if (G->adjList[i].indegree == 0) {
            stack[++top] = i;
        }
    }
    
    while (top != -1) {
        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，如果变成0就入栈
            if (--G->adjList[k].indegree == 0) {
                stack[++top] = k;
            }
        }
    }
    
    if (count < G->numVertexes) {
        printf("图中有环，拓扑排序失败！\n");
        return 0;
    }
    return 1;
}

你想想看，如果图里有环会怎样？算法执行到最后，一定会有顶点入度不为0，但已经没有入度为0的顶点了。这时候count一定小于总顶点数，我们就知道——图里有环！

二、AOE网与关键路径

AOE网和AOV网不一样。AOE是Activity On Edge，用顶点表示事件，用边表示活动，边的权值表示活动持续时间。AOE网通常用来估算整个工程的最短工期。

我记得有一次做软件开发的项目管理，要估算整个项目的最短完成时间。当时我就用AOE网建模，把每个开发任务当作一条边，任务的预估工时作为权值，然后计算关键路径。结果发现有个测试环节居然在关键路径上，一旦延期就会拖累整个项目。

几个重要概念

在计算关键路径之前，需要先理解四个时间参数：

参数	含义	计算公式
etv[k]	事件k的最早发生时间	etv[k] = max(etv[i] + weight<i,k>)
ltv[k]	事件k的最晚发生时间	ltv[k] = min(ltv[j] - weight<k,j>)
ete[i]	活动i的最早开始时间	ete[i] = etv[活动起点]
lte[i]	活动i的最晚开始时间	lte[i] = ltv[活动终点] - weight

当ete[i] == lte[i]时，这个活动就是关键活动。所有关键活动连起来，就是关键路径。

三、关键路径算法实现

算法分三步走：

1. 对AOE网进行拓扑排序，同时计算每个事件的最早发生时间etv
2. 逆拓扑序计算每个事件的最晚发生时间ltv
3. 遍历所有活动，计算ete和lte，找出关键活动

// 关键路径算法
int CriticalPath(GraphAdjList *G) {
    int stack[MAX_VERTEX], top = -1;
    int etv[MAX_VERTEX] = {0};  // 最早发生时间
    int ltv[MAX_VERTEX];        // 最晚发生时间
    int topoStack[MAX_VERTEX];  // 存储拓扑序列
    int topoTop = -1;
    int count = 0;
    
    // 第一步：拓扑排序并计算etv
    for (int i = 0; i < G->numVertexes; i++) {
        if (G->adjList[i].indegree == 0) {
            stack[++top] = i;
        }
    }
    
    while (top != -1) {
        int gettop = stack[top--];
        topoStack[++topoTop] = gettop;
        count++;
        
        for (EdgeNode *e = G->adjList[gettop].firstedge; e; e = e->next) {
            int k = e->adjvex;
            if (--G->adjList[k].indegree == 0) {
                stack[++top] = k;
            }
            // 更新最早发生时间
            if (etv[gettop] + e->weight > etv[k]) {
                etv[k] = etv[gettop] + e->weight;
            }
        }
    }
    
    if (count < G->numVertexes) return 0;
    
    // 第二步：初始化ltv
    for (int i = 0; i < G->numVertexes; i++) {
        ltv[i] = etv[G->numVertexes - 1];
    }
    
    // 逆拓扑序计算ltv
    while (topoTop != -1) {
        int gettop = topoStack[topoTop--];
        for (EdgeNode *e = G->adjList[gettop].firstedge; e; e = e->next) {
            int k = e->adjvex;
            if (ltv[k] - e->weight < ltv[gettop]) {
                ltv[gettop] = ltv[k] - e->weight;
            }
        }
    }
    
    // 第三步：找出关键活动
    printf("关键路径：\n");
    for (int i = 0; i < G->numVertexes; i++) {
        for (EdgeNode *e = G->adjList[i].firstedge; e; e = e->next) {
            int k = e->adjvex;
            int ete = etv[i];
            int lte = ltv[k] - e->weight;
            if (ete == lte) {
                printf("<%d, %d> 权值:%d\n", 
                       G->adjList[i].data, 
                       G->adjList[k].data, 
                       e->weight);
            }
        }
    }
    return 1;
}

四、知识体系总览

下面这张图把本章的核心知识点串起来了，你可以对照着看：

你看，AOV网和AOE网虽然名字相似，但解决的问题完全不同。AOV网关心的是「能不能做」——活动之间的依赖关系是否合理；AOE网关心的是「多久做完」——整个工程的最短工期是多少。

我个人觉得，理解关键路径算法的关键在于把握住「最早」和「最晚」这两个时间概念。最早时间是从前往后推，取最大值；最晚时间是从后往前推，取最小值。方向搞反了，结果就全错了。

好了，拓扑排序和关键路径就讲到这里。代码我已经贴出来了，建议你动手跑一遍，把etv和ltv的值打印出来看看，这样理解会更深刻。