图综合练习--拓扑排序_学习数据结构——第五章：图（图的应用02）

3.拓扑排序

如上图，表示的就是我们只有学习了计算机基础，才能学习程序语言，然后才能学习数据结构接着才能学习算法分析，我们如果按照发生顺序对他们进行排序的话：计算机基础-程序语言-数据结构-算法分析，得到的这个序列就是拓扑排序序列。首先我们需要了解：

有向无环图：不存在环的有向图,简称DAG图。

AOV网：若用一个.AG图表示一个工程，其顶点表示活动，用有向边表示活动 vi 先于活动 vj 进行的传递关系，则将这种DAG称为顶点表示活动网络，记为AOV网。(虽然它叫网，但是它的边是没有权值的)

拓扑排序：对DAG所有顶点的一种排序，使若存在一条从顶点A到顶点B的路径，在排序中B排在A的后面

算法思想

• 1)从DAG图中选择一个没有前驱的顶点并输出
• 2)从图中删除该顶点和所有以它为起点的有向边
• 3)重复1)、2)直到当前的DAG图为空或当前图中不存在无前驱的顶点为止。后一种情况说明图中有环(则不是有向无环图)。

我们知道每次我们删除的是顶点入度为0的顶点，所以我们用一个辅助数组来标记当前顶点的入度，然后找出值为0的下标，我们发现是顶点0，所以我们删除顶点0，输出，并删除0顶点对应的所有的出边

然后我们要修改数组，

，接着我们继续找值为0的下标，我们发现是1顶点，接着我们删除1顶点，输出，并删除1顶点对应的所有的出边

删除之后我们依旧要修改数组，

，继续找值为0的下标，我们发现是2顶点，然后我们删除2顶点，输出，并删除2顶点对应的所有的出边

同样删除之后修改数组，

，最后还剩3顶点，同样删除，输出。这样我们就得到这个有向无环图的拓扑排序序列：{0，1，2，3}。我们下面看一个有环的例子

同样首先我们初始化一个数组

，然后找到值为0的顶点0，接着删除顶点0，并输出，并删除顶点0对应的出边

然后修改数组：

，然后我们发现没有顶点的入度为0，即为算法描述中第三个步骤当前图中不存在无前驱的顶点，此时图为有环图。

即：算法结束时没有访问所有顶点，则存在以剩下顶点组成的环。

然后我们继续看一个例子：

首先我们初始化一个数组：

，然后找出值为0的顶点，找到了0顶点，然后删除0顶点，输出，并删除0顶点对应的出边

接着修改数组：

，此时我们发现有两个顶点的入度都为0，此时选择那个一个顶点先开始都可以，那么到最后我们发现此有向无环图有两种拓扑排序的序列：{0，1，2，3} 或 {0，2，1，3}

即：拓扑排序的结果不一定唯一

代码实现，时间复杂度：O(V+E)

拓扑排序的特点：

• 若邻接矩阵为三角矩阵，则存在拓扑排序；反之不一定成立

例如：

，上三角矩阵，它如果是某一个有向图的邻接矩阵的话，则对应在该有向图中一定满足如下条件：Vi->Vj中的i

反之不一定成立因为比如：0->2，2->1，我们也可以得到一个拓扑排序序列，但是这个图对应的邻接矩阵不是一个三角矩阵。

4.关键路径

上面我们讲解了拓扑排序的AVO网这里我们讲另外一种网AOE网，使用每一个有向边表示活动，权值常常代表一个活动所需要的金钱或者时间开销等等，顶点表示的是事件

AOE网：在有向带权图中，以顶点表示事件，以有向边表示活动，以边上权值表示完成该活动的开销(如完成活动所需要的时间)，则称这种有向图为用边表示活动的网络，简称AOE网

上面讲的AOV网是没有权重的

AOE网有以下特点：

• 它始终只有一个顶点是完全没有入边的，我们称为源点，如上图的V1
• 它始终只有一个顶点是完全没有出边的，我们称为汇点，如上图的V6

顶点与入边的关系：如上图V4顶点和入边a3、a5，边代表活动，点代表事件，只有a3和a5的活动都结束才能开始V4顶点的事件(上图V2和V3事件同时开始)

顶点与出边的关系：如上图V4顶点和出边a7，表示只有V4顶点的事件完成后才能进行a7活动

关键路径：从原点到汇点最大路径长度的路径(权重和最大的路径)称为关键路径，关键路径上的活动为 关键活动

关键路径为什么关键？我们知道例如一个工程，关键路径上的关键活动直接决定的工程的完成事件，我们知道了关键路径，我们就可以进行优化关键路径，提升工程的完成效率等等

4.1关键路径的计算

1、事件Vk的最早发生时间Ve(k)

我们可以看一下图中的顶点V4，从V1到顶点V4(我们默认V1耗时为0)，有两条路径：V1->V2->V4；V1->V3->V4；路径1耗时3+2=5，路径2耗时2+4=6；那么事件V4最早发生时间是？这时可能有人会说5小时，其实答案是6，因为事件V4的发生必须满足a3和a5同时完成。

Ve(源点)=0; Ve(k)=Max{Ve(j)+Weight(Vj,Vk)}

Weight(Vj,Vk)：顶点Vj到当前顶入边的权值

上图各个顶点的最早发生时间

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

解释：我们在不推迟整个工程的完成时间的情况下，每个事件它最迟可以什么时间开始

计算方式其实和最早发生事件是相反的，我们从汇点向源点。

Vl(汇点)=Ve(汇点);//令汇点的最迟发生时间等于汇点的最早发生时间，如果我们汇点的最迟发生时间大于汇点的最早发生时间那么我们就等于推迟了工程的结束时间，所以只能相等

Vl(j)=Min{Vl(k)-Weight(Vj,Vk)} 我们计算最早发生时间使用了入边，这里我们使用出边向源点进行逆推。

例如：Vl(2)的最迟发生时间，我们可以使用Ve(4)-a3=4和Ve(5)-a4=3进行比较找出最小值

上图各个顶点的最迟发发生时间

3、活动ai的最早开始时间e(i)

我们知道每一个事件所需事件为0，那么每一个活动的最早开始时间就是整个活动的弧的弧头这个事件的最早开始时间即

若存在表示活动ai，则e(i)=Ve(k)

我们只需找到每个事件的最早开始时间，然后对应每个活动即可找到每个活动的最早开始时间

4、活动ai的最迟开始时间l(j)

若存在表示活动ai，则l(i)=Vl(j)-Weight(Vk,Vj)

我们只需找到每个事件的最迟开始时间，然后依次计算每个活动的最迟开始时间：例如a1的最迟开始时间等于Vl2-a1的权重=4-3=1

5、活动ai的差额d(i)=l(i)-e(i)

最迟发生时间减去最早发生时间等与活动的差额，我们先计算出每个活动的最迟发生时间和最早发生时间然后做个减法

我们通过活动的差额可以找到关键活动，其中值为零的就是关键活动，值为零说明此活动的最迟发生时间和最早发生时间相同，对于这些活动我们不能早开始也不能晚开始，都会影响整个工程的时间，这些活动当然就是工程的关键活动，我们利用这些关键活动可以组成关键路径：V1->V3->V4->V6，我们如果想优化整个工程就要优化整个工程的关键路径上的关键活动。

注意：缩短关键活动时间可以加快整个工程，但缩短到一定大小时关键路径会发生改变

例子：

在该AOE网中有以下关键活动路径：{a2，a4，a3，a7}；{a2，a4，a5，a8}；{a2,a6,a8}

由此可以看出不是所有的AOE网只有一条关键路径，其实AOE网可能有多条关键路径。那么就出现了一个问题，如果我们想要缩减整个工程的时间的话，如果只缩减一条关键路径上的关键活动就可以吗？答案是可能可以，如果该关键活动包含在所有的关键活动中。就如上图，如果我们缩减a2即可达到缩减整个工程的目的。但是如果我们缩减a5，不能改变整个工程的时间。

即：当网中关键路径不唯一时,只有加快的关键活动或关键活动组合包括在所有的关键路径上才能缩短工期。

7.理木客

数据结构相关知识，公众号理木客同步更新中，欢迎关注