6.6 拓扑排序与关键路径

有向无环图与表达式，AOV 网的拓扑排序，AOE 网中事件与活动的时间计算及关键路径。

有向无环图描述表达式

若一个有向图中不存在环，则称为有向无环图，简称 DAG。

有向无环图是描述含有公共子式的表达式的有效工具。例如表达式 $((a+b) \times (b \times (c+d)) + (c+d) \times e) \times ((c+d) \times e)$，若用二叉树表示，则其中的相同子式 $(c+d)$ 和 $(c+d) \times e$ 会重复出现；若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间。

拓扑排序

AOV 网：若用 DAG 表示一个工程，其顶点表示活动，用有向边 $\langle V_i, V_j \rangle$ 表示活动 $V_i$ 必须先于活动 $V_j$ 进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为 AOV 网。在 AOV 网中，活动 $V_i$ 是活动 $V_j$ 的直接前驱，活动 $V_j$ 是活动 $V_i$ 的直接后继，这种前驱和后继关系具有传递性，且任何活动 $V_i$ 不能以它自己作为自己的前驱或后继。

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

1. 每个顶点出现且只出现一次；
2. 若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径。

对一个 AOV 网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：

1bool TopologicalSort(Graph G) {
2    InitStack(S);
3    for (int i = 0; i < G.vexnum; i++)
4        if (indegree[i] == 0)
5            Push(S, i);            // 所有入度为 0 的顶点入栈
6    int count = 0;
7    while (!IsEmpty(S)) {
8        Pop(S, i);
9        print[count++] = i;        // 输出顶点 i
10        for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
11            v = p->adjvex;         // 将 i 指向的顶点入度减 1
12            if (!(--indegree[v]))
13                Push(S, v);        // 入度为 0 则入栈
14        }
15    }
16    return count == G.vexnum;      // count < n 说明有回路
17}

逆拓扑排序：每次输出出度为 0 的顶点，删除它和所有以它为终点的有向边。利用 DFS 也能实现逆拓扑排序——在顶点退出递归时输出。

关键路径

AOE 网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称 AOE 网。

AOE 网具有以下两个性质：

1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

在 AOE 网中仅有一个入度为 0 的顶点，称为开始顶点（源点），它表示整个工程的开始；网中也仅存在一个出度为 0 的顶点，称为结束顶点（汇点），它表示整个工程的结束。

从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。

五个量

1// ① 按拓扑序求事件最早发生时间 ve
2ve(源点) = 0;
3ve(k) = max{ ve(j) + Weight(vj, vk) }   // vj 为 vk 的任意前驱
4// ② 按逆拓扑序求事件最迟发生时间 vl
5vl(汇点) = ve(汇点);
6vl(k) = min{ vl(j) - Weight(vk, vj) }   // vj 为 vk 的任意后继
7// ③ 活动 ai = <vk, vj> 的最早开始时间 e 与最迟开始时间 l
8e(i) = ve(k);
9l(i) = vl(j) - Weight(vk, vj);
10// ④ d(i) = l(i) - e(i)，d(i) == 0 的活动为关键活动

本例的关键路径为 $V_1 \to V_3 \to V_4 \to V_6$，关键活动为 $a_2, a_5, a_7$，工程最短完成时间为 8。

即时练习