拓扑排序和关键路径

AOV 和 AOE

DAG：有向无环图
AOV 网：有向无环图中，使用顶点表示活动，边表示依赖关系，则称为「顶点表示活动的网络」。
AOE 网：有向无环图中，以顶点表示时间，边表示活动，边的权值表示活动的开销，这种图成为「用边表示活动的图」。

拓扑排序

拓扑排序是指对「有向无环图」顶点的一个排序。排在前面的顶点不依赖后方的顶点。

注：使用「邻接矩阵」存储有向图时，如果存储结构为三角矩阵，那么一定存在拓扑序列。

方法1：逐个删除节点

思路：找到图中入度为 的顶点，输出，并删除该顶点发出的边。重复这个过程。
注：如果最后还剩下顶点，说明图中存在环。

逆拓扑排序：找到图中出度为 的顶点，输出，并删除该顶点的所有入边，重复这个过程。

方法2：深搜

需要对深搜做一下调整：在回溯时才输出结点，得到的序列即为拓扑排序的逆序列。

• 上图调整过的深搜结果为：E, C, D, B, A
• 则其拓扑排序的序列为：A, B, D, C, E

关键路径

AOE 网用顶点表示事件，边表示活动，具有以下性质：

• 只有事件依赖的所有活动都完成时，事件才会发生
• 只有事件发生后，其后的活动才能开展

相关概念

关键路径：AOE 网中，只有一个源点（入度为 的点）和一个汇点（出度为 的点）。从源点到汇点有多条路径，开销最大的路径即为关键路径。（因为所有活动都是任务的一部分，都需要完成，所以用关键路径来衡量任务的总时常）

有以下几个辅助概念：
事件 最早发生时间 ：

• 也就是从源点到事件节点 的最长路径，表示事件最早什么时候可以开工。
• 计算方法为：
• 其中， 是 的任意前驱，按照拓扑排序的顺序从前往后递推计算。

事件 最迟发生时间 ：

• 也就是找到 到终点的最长路径，表示事件最多可以推迟到什么时候开工。
• 计算方法为：
• 其中， 是 的任意后继，按照逆拓扑排序的顺序从后往前递推计算。

活动 的最早开始时间：事件发生了，活动就发生了。如果边 代表活动 ，那么活动最早开始时间为：

活动 的最迟开始时间：只要在后序事件最迟发生时间之前完成活动即可。如果边 代表活动，那么活动最迟开始时间为：

关键活动：活动有「最早开始时间」和「最迟开始时间」，如果两者相等，则对应活动为「关键活动」。

求解关键路径

求解步骤：

• 得到拓扑序列
• 根据拓扑序列求出「事件最早发生时间」和「事件最迟发生时间」
• 计算出「活动最早开始时间」和「活动最迟开始时间」
• 找到「活动最早开始时间」和「活动最迟开始时间」相等的关键活动，关键活动组成了关键路径。

注：（不太好证明）

1. 关键路径上的事件，「最早发生时间」等于「最晚发生时间」。
2. 关键活动一定位于关键路径中。