拓扑排序

一、定义

AOV 网（Activity On Vertex Network）：用顶点表示活动，边表示活动的先后关系，是有向无环图（DAG）。

拓扑排序：对 DAG 的顶点进行线性排序，使得对任意有向边 $\langle u,v\rangle$，$u$ 在序列中出现在 $v$ 之前。

二、算法步骤

1. 选一个入度为 0 的顶点，输出
2. 删除该顶点及所有出边
3. 重复，直到：所有顶点输出 ⟹ 排序成功；无入度为 0 但仍有顶点 ⟹ 有环

三、代码实现（邻接表）

bool TopologicalSort(ALGraph G) {
    int indegree[MaxVertexNum];
    SqStack S; InitStack(&S);
    for (int i = 0; i < G.vexnum; i++) {
        indegree[i] = 0;
        ArcNode *p = G.vertices[i].first;
        while (p) { indegree[p->adjvex]++; p = p->next; }
    }
    for (int i = 0; i < G.vexnum; i++)
        if (indegree[i] == 0) Push(&S, i);
    int count = 0;
    while (!StackEmpty(S)) {
        Pop(&S, &v); printf("%d ", v); count++;
        ArcNode *p = G.vertices[v].first;
        while (p) {
            indegree[p->adjvex]--;
            if (indegree[p->adjvex] == 0) Push(&S, p->adjvex);
            p = p->next;
        }
    }
    return (count == G.vexnum);   // false 表示有环
}

时间复杂度 $O(|V|+|E|)$。

四、应用

• 判断有向图是否有环：拓扑排序能否输出所有顶点
• 求关键路径（AOE 网）：拓扑排序求事件最早发生时间，逆拓扑求最迟发生时间

五、拓扑序列不唯一

同一时刻可能有多个入度为 0 的顶点，选择不同导致序列不同；唯一性条件：每个步骤只有一个入度为 0 的顶点可选。

例 1：拓扑排序

A → B → D
|       ↑
↓       |
C → E → F

入度：A0, B1, C1, D2, E1, F1。依次选 A→B→→D 等，拓扑序列 A B C E F D（不唯一）。

例 2：判断有环

A → B → C → A

入度：A1, B1, C1，无入度为 0 的顶点 ⟹ 有环！

例 3：所有拓扑序列

A → C   A → D
B → C   B → D

入度：A0, B0, C2, D2。可能序列：A B C D、A B D C、B A C D、B A D C，共 4 种。

本例中 A、D、E 能正常拓扑排出；B 与 C 互相指向，入度永远无法降到 0，故被标红——这正是“有环”的判定依据。