数据结构之拓扑排序、关键路径

本文内容包括：拓扑排序、关键路径

一、拓扑排序

在讲到拓扑排序之前，我们得先了解一下有向无环图、AOV网和AOE网这三个东西

有向无环图（DAG）：

中间的就是有向无环图，自己对比一下

AOV网和AOE网：

AOV网用于拓扑排序，AOE网用于关键路径。

引例1：

排课表问题。我们需要确定哪一门课先修，哪一门课得在前一门课的基础上修

引例2：

如何判断一个有向图是否有环？

拓扑排序出场

对下面这个图进行拓扑排序，得到的序列用来设置课程表，就是合理的

拓扑排序思想核心：每次找出入度为0的节点，将其加入到拓扑序列中，然后删掉其所有的出度。

…
一直到将所有节点全部加入到拓扑序列中，算法完成。

最后你可能会得到多种结果，即拓扑序列不是唯一的。

拓扑排序也可以用来解决我们引例2中的问题

如果最后得到一个环路，无法再进行删除了，那么就说明该AOV网有向图中存在环

二、关键路径

上文我们说过，AOV网用于拓扑排序，AOE网用于关键路径。

注意，AOE网中，弧用来表示活动，弧上面的权值代表活动时间，点代表事件

如何确定关键路径，需要定义四个描述量

下面开始举例子：

1、事件的最早开始时间Ve

对于这样一个AOE网，Vj的最早开始时间是：88.

为什么呢？很直观，因为Vj想要发生，必须得等到3、5、12、88全部都做完，而V1这个事件默认是在0时刻开始的，因此，Vj最早开始时间是取最大值88.

好比：你是一个厨师，需要做一锅胡萝卜炖羊肉，于是你请你的4个徒弟去买菜。A徒弟3分钟买回来了胡萝卜，B徒弟5分钟买回了葱姜蒜，C徒弟12分钟买回了各种香料，唯独D徒弟的羊肉迟迟没有买回来，那请问，你连羊肉都没有，怎么可能开始做菜？于是，你等啊等，等了88分钟，D徒弟终于买回了羊肉，于是你才能开始做菜，Vj事件才能开始执行！

所以请记住，Ve(Vj)表示事件Vj的最早开始时间。

2、事件的最迟发生时间Vl(Vj)

最迟发生时间反过来，要从汇点去推源点

所以这里上面Vj最迟发生时间是10 - 7 = 3；

即：要满足Vn在10这个时刻能发生，那么，Vj最迟得在3时刻开始

会找节点的最早开始时间和最迟发生时间之后，我们就可以来算出各条边的最早开始、最迟发生时间了

如下面这个图
各条边（活动）的最早开始，最迟发生：

所谓关键活动就是：最早开始时间和最迟发生时间相等的活动。
满足 l - e == 0
因为“关键”的意思就是，一刻不能耽误，必须马上开始。

举个例子
比如：我今天出去参加会议，如果说会议的最早入场时间是14:00，最迟入场时间是14:30，超过14:30就不能进场了，那么这个会议活动其实算不上关键活动，因为我可以在14:15或者14:20进场，而非一定得在14:00时刻进场。

但如果这个会议最早入场时间是14:00，且最迟入场时间也是14:00，一刻都不能耽误，那么，这个活动就是关键活动

那么在AOE网中，由关键活动构成的一条路径，就是关键路径了
根据上面的分析，图中关键路径有两条，蓝颜色的。