12. 图高级应用：拓扑排序、关键路径、AOE网、图的连通性问题

图这个数据结构，说实话，越往后学越有意思。前面我们聊了图的遍历、最短路径、最小生成树，那些都是基础中的基础。但真正到了工程里，你会发现图的威力远不止这些。今天我要讲的这几个话题——拓扑排序、关键路径、AOE网、连通性问题——说白了，就是图论里最贴近实战的那部分。

我记得刚入行那会儿，接手一个项目排期系统，老板让我算「整个项目最快什么时候能做完」。我当时第一反应就是「关键路径」。嗯，没错，就是今天要讲的核心内容之一。你想想看，一个项目几百个任务，哪个环节拖不得？哪个任务可以摸鱼？这些问题的答案，全在图里。

12.1 拓扑排序：有向无环图的线性化

先说说拓扑排序。这个概念其实不复杂：把有向无环图（DAG）的所有顶点排成一个线性序列，使得图中任意一条有向边的起点都在终点之前。说白了，就是给一堆有依赖关系的任务排个序。

举个例子：你要做一道菜，得先洗菜、切菜，然后才能炒菜。洗菜和切菜之间没有依赖关系，可以并行。拓扑排序就是找出这样一个合理的执行顺序。

12.1.1 算法实现：Kahn算法

我个人习惯用Kahn算法来实现拓扑排序。它的思路很直观：每次从图中取出一个入度为0的顶点，然后删除它和它的出边，重复这个过程。直到所有顶点都被取出，或者发现还有顶点剩余（说明有环）。

我在项目中遇到过一个问题：一个大型软件模块的编译依赖图，有上千个节点。用Kahn算法跑一遍，几毫秒就出结果了。但如果你用DFS递归去做，栈可能会爆掉。所以，工程上我推荐用Kahn算法。

// Kahn算法实现拓扑排序
// 返回排序后的顶点序列，如果存在环则返回空
int* topologicalSort(Graph* g, int* returnSize) {
    int n = g->vertexCount;
    int* inDegree = (int*)calloc(n, sizeof(int));
    int* result = (int*)malloc(n * sizeof(int));
    int front = 0, rear = 0;
    
    // 计算所有顶点的入度
    for (int i = 0; i < n; i++) {
        EdgeNode* p = g->adjList[i].firstEdge;
        while (p) {
            inDegree[p->adjVex]++;
            p = p->next;
        }
    }
    
    // 将所有入度为0的顶点入队
    int* queue = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }
    
    int count = 0;
    while (front < rear) {
        int u = queue[front++];
        result[count++] = u;
        
        EdgeNode* p = g->adjList[u].firstEdge;
        while (p) {
            int v = p->adjVex;
            if (--inDegree[v] == 0) {
                queue[rear++] = v;
            }
            p = p->next;
        }
    }
    
    free(inDegree);
    free(queue);
    
    if (count != n) {
        // 存在环，返回空
        free(result);
        *returnSize = 0;
        return NULL;
    }
    
    *returnSize = n;
    return result;
}

12.2 AOE网与关键路径

好，接下来是重头戏——AOE网和关键路径。AOE网（Activity On Edge network）是一种带权有向无环图，顶点表示事件，边表示活动，边的权值表示活动的持续时间。你想想看，这不就是项目排期的天然模型吗？

关键路径，就是AOE网中从源点到汇点路径长度最长的路径。为什么最长路径反而叫「关键」？因为这条路径上的任何一个活动延误了，整个项目的完成时间就会延误。说白了，关键路径上的活动一个都不能拖。

12.2.1 四个关键参数

要找出关键路径，我们需要计算四个参数。我建议你记住它们，因为面试常考，项目里也常用：

参数	含义	计算公式
ve(v)	事件v的最早发生时间	ve(v) = max{ve(u) + w(u,v)}
vl(v)	事件v的最晚发生时间	vl(v) = min{vl(w) - w(v,w)}
e(a)	活动a的最早开始时间	e(a) = ve(u)
l(a)	活动a的最晚开始时间	l(a) = vl(v) - w(u,v)

其中，关键活动就是 e(a) == l(a) 的活动。所有关键活动组成的路径，就是关键路径。

12.2.2 计算步骤

我个人习惯分三步走：

1. 先做拓扑排序，按拓扑序计算所有事件的最早发生时间 ve
2. 再做逆拓扑排序，按逆拓扑序计算所有事件的最晚发生时间 vl
3. 最后遍历所有边，计算每个活动的 e 和 l，找出 e == l 的活动

我曾经在一个芯片设计项目中用这套方法做时序分析。那个项目有上万个逻辑门，每个门都有延迟。用AOE网建模后，关键路径一算出来，我们就知道哪些路径需要优化。嗯，那次项目最后提前了两周交付，关键路径分析功不可没。

12.3 图的连通性问题

连通性问题，听起来简单，但实际应用里坑不少。我把它分成两类来说：无向图的连通分量和有向图的强连通分量。

12.3.1 无向图的连通分量

无向图的连通分量，说白了就是图里「连成一片」的那些子图。判断方法很简单：从任意顶点出发做DFS或BFS，能访问到的所有顶点构成一个连通分量。然后换一个没访问过的顶点继续，直到所有顶点都被访问过。

这个在社交网络分析里特别有用。我记得做过一个用户关系分析项目，几百万用户的关系图，用并查集（Union-Find）做连通分量分析，效率非常高。

12.3.2 有向图的强连通分量

有向图的强连通分量（SCC）就复杂一些了。它要求分量内任意两个顶点之间互相可达。你想想看，这比无向图的连通分量要求严格多了。

最经典的算法是Tarjan算法，基于DFS，用时间戳和栈来识别SCC。还有一个是Kosaraju算法，需要做两次DFS，第一次在原图上，第二次在反向图上。

我个人更推荐Tarjan算法，因为它只需要一次DFS，效率更高。不过Kosaraju算法理解起来更直观一些。看你的个人喜好了。

// Tarjan算法求强连通分量（伪代码框架）
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stack.push(u);
    inStack[u] = true;
    
    for (每个邻接点v) {
        if (!dfn[v]) {          // v未被访问
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) { // v在栈中，说明是回边
            low[u] = min(low[u], dfn[v]);
        }
    }
    
    if (dfn[u] == low[u]) {
        // 找到一个强连通分量
        sccCount++;
        do {
            v = stack.pop();
            inStack[v] = false;
            belong[v] = sccCount;
        } while (v != u);
    }
}

12.4 知识体系总览

说了这么多，我画了一张图帮你理清思路。这张图展示了本章四个核心知识点之间的关系：

12.5 避坑指南与实战经验

最后，我分享几个实战中踩过的坑，希望能帮你少走弯路：

好了，这一章的内容就到这里。图的高级应用，说白了就是「把现实问题抽象成图，然后用算法求解」。拓扑排序解决依赖问题，关键路径解决工期问题，连通性解决关系问题。掌握了这些，你就能用图论解决很多实际工程问题了。

---

公众号:蓝海资料掘金营，微信deep3321