7.5.1 拓扑排序在线视频

同学们，大家好

我是云南大学信息学院教师孔兵

这节课，我们讨论有向无环图及应用

有向无环图，顾名思义，就是是一个有向图

但是图中没有环，没有回路，简称DAG图

例如幻灯片所示的三个图，都属于有向无环图

有向无环图可以作为描述工程项目或者是系统的一个工具

以工程项目为例，一般工程项目都是很复杂的

可以把工程项目分解为一些活动

这些活动都完成了，那么工程项目也就完成了

这活动之间，可能有一定的约束关系

也就是它们的执行有先后次序

比如说建造一栋房屋，可能有向地质勘探

建筑设计，工程预算，材料采购，人员雇佣

基础施工，水电安装等等

这些都建造一栋房屋需要完成的活动

这些活动完成了，房屋也就建好了

但这些活动之间是有约束的

首先得做地质勘探，搞清楚建设用地的地质条件

在这个基础上，才能考虑怎么做建筑设计的问题

同样，有了设计，才能根据设计做出预算

我们讨论的有向无环图，有两类

一是顶点表示活动的AOV网，AOV网中

每个顶点表示一个活动

用弧表示它们之间的一个约束关系

比如说示例图中，v1到v2，v3有弧

意思是v1这个活动完成以后

v2和v3这两个活动才能开始

v2和v3两个活动都完成以后

v4这个活动才能开始

弧体现了活动之间的一个约束关系

另外一种呢，是边表示活动的网

称为AOE网，在网中，一条边表示一个活动

活动带个权值，这个权值表示完成活动需要的时间

AOE网的顶点表示的是事件

表示某个事件发生了

这个问题，后面我们再详细讨论

讨论有向无环图，主要是想解决两个问题

一是，工程能否顺利进行？

对这个问题，我们是基于AOV网

利用拓扑排序算法判断工程是否能顺利进行

其核心是发现AOV网中是否有环

如果AOV网中有环，说明工程安排出错了

二是，估算整个工程完成所必须的最短时间

并且找出工程当中的关键活动

这个问题我们是基于AOE网，利用关键路径算法来实现的

下面先讨论AOV网和拓扑排序

AOV网中用顶点表示活动，用弧表示活动间的优先关系

这样的有向图称为顶点表示活动的网简称AOV网

网中顶点i到顶点j有一条有向路径

则i是j的前驱；j是i的后继

若i到 j是网中一条弧，

则i是j的直接前驱

j是i的直接后继

一个顶点i到另外一个顶点j有一条有向路径

意味着活动i对活动j有约束

这样的约束可能是直接的

比如说i到j有一条弧

也可能是间接的

就是i到j有一条有向路径

如图中，v1,v3,v5,v7是一条路径

那么这条路径的活动之间，前驱对后继有约束

活动必须按顶点的次序先后来完成

例如v3必须在v1完成后才可能开始

不是必然能开始，还有v4对它的约束

当然有的活动之间没有约束

如v2和v3，它们之间没有路径

这两个活动执行的相对次序随意

下面我们看一个AOV网的实例

可以称为学习流图

图中每个顶点是一门课程

顶点表示的是学习课程的活动

弧 表示的是课程之间学习的一个先后的次序

顶点C3的意思是学习数据结构，按图中的约束关系

需要在学习了C1程序设计基础和C2离散数学的基础上

才能学习数据结构

C1程序设计基础和C9高等数学

在大学教学中是可以马上学习的

从这个图中，可以看到课程学习活动之间的约束关系

拓扑排序就是要发现这样的AOV网中是否有环

采用的办法是模拟项目的执行过程

拓扑排序的步骤，有以下几步

一是在有向图中选一个没有前驱的顶点

且输出之，所谓没有前驱的顶点意味着没有约束

可以马上开始执行

例如程序设计课程的学习

建造房屋的地质勘探

拓扑排序是对执行过程的模拟

那么，这里的所谓输出之

意思就是说这把这个活动完成

二是从图中删除该顶点和所有以它为尾的弧

删除该顶点

意思就是模拟活动完成

删除所有以它为尾的弧

这个活动既然已经完成

那么它对后继的约束也就消失了

作为描述约束的弧也就可以取消了

拓扑排序就是重复一二两步，直至全部顶点均已输出

或者当前图中不存在无前驱的顶点为止

下面我们就通过具体的AOV网看一下拓扑排序的过程

这个AOV网中，有两个没有前驱的顶点

v1和v6,我们选取一个v1，输出v1

表示v1活动完成了，然后从图中删除所有以v1为尾的弧

删除以后的情况如图2所示

图2中，没有前驱的顶点又增加了一个v3

因为v1的约束没有了

我们输出v3

删除以v3为尾的弧

结果如图3所示

无前驱的顶点有v2和v6

输出v2

删除以v2为尾的弧

情况如图4所示

没有前驱的顶点只有v6

输出v6

输出v4，最后输出v1

这样的我们就获得了AOV网的拓扑排序序列

v1，v3，v2，v6，v4，v5

现在图中所有的顶点都被输出

说明通过模拟工程的执行过程了

工程是可以顺利执行的

关于拓扑序列，有两个问题我们要说明一下

一是拓扑序列不是唯一的

从刚才拓扑排序的过程中，同学们可能注意到了

很多时候我们是有选择的，比如说第1个排序的

我们选择了v1，实际上v6也可以作为第1排序的顶点

在后续过程当中，还有很多时候可以选择

不同的选择会导致，最终的拓扑序列是不一样的

二是拓扑序列虽然不同，但拓扑序列一定保持约束的

也就是说如果顶点i是顶点j的前驱

不管是直接还是间接的，拓扑序列中i一定在j之前

不一定紧邻，但是相对位置i一定在j之前

那么，什么情况下，没有能输出全部顶点

但是图中不存在无前驱的顶点呢

看一下图，三个顶点之间形成了环

没有无前驱的顶点

这样的约束导致没有任何活动可以开始进行

模拟进行不下去了

当然这样的环不一定是三个顶点

可能是很多个顶点

如果AOV网当中有这样的环

那么说明在工程活动的安排上肯定发生了错误

下面，我们结合刚才讨论的这个例子

说一下拓扑排序算法的实现

这个算法很重要

后面的关键路径算法也是在这个算法的基础上实现的

算法中并不删除图中的顶点和弧

而是通过一个记录顶点入度的数组来处理

拓扑排序算法中，核心有两个数据结构

一是一个叫indegree的一维数组

这个数组用来记录图中每个顶点的入度

图1中indegree是初始化以后的结果

可以看到，对应以v1的0号单元

和对应v6的5号单元，它们的入度为0

其它单元中是各个顶点的入度

有向图我们用的是邻接表的存储方式

邻接表是用指后继的方式描述关系

方便求出度，那么怎么求出所有顶点的入度呢？

我们不是以找前驱的方式求

而是用找后继的方式来求

入度数组初始化的时候

所有顶点的入度均置为0

然后，对有向图的邻接表做一次二维扫描

考察每个顶点以及它对应的单链表

找到它的后继位置，把入度数组中对应的单元加1

完成扫描以后，入度数组中，就是每个顶点的入度了

第2个重要的结构是一个栈S

栈中存储入度为0的顶点

初始化完成以后

把入度为零的顶点入栈

就我们的例子来说

入度为0的点有两个，一个是v1，一个是v6

我们把它们的存储位置0和5入栈

拓扑排序的算法的关键步骤是一个单循环

当栈S不空的时候，把栈顶元素出栈到i中

这是我们排序的第1个顶点，如图2所示

输出第一个顶点的位置i，以及i对应的顶点

这里是位置5和顶点v6

随后，循环考察输出顶点的每个后继

设后继位置为k，入度数组k号单元减1

如果减1以后，indegree[k]为0

则把后继顶点k入栈S，v6的后继是v4和v5

把入度数组中3号和4号单元减1

其含义就是删除以v6为尾到v4和v5的这两条弧

减1以后两个顶点的入度为1和2，不入栈

现在栈中只有一个顶点v1，位置为0

把这个0出栈，输出位置0和它对应的顶点v1

随后考察v1的所有后继，v1的后继有v2,v3,v4

入度数组单元1,2,3减1后，2和3号单元为0，入栈

下一次循环时，3号单元v4顶点出栈

后续的过程就不重复了

图7中，输出1号单元的v2后

下次循环栈为空，循环结束

示例图中没有环，所有的顶点都输出了

拓扑排序的过程结束了

下面我们看一下拓扑排序的函数

拓扑排序的函数中，首先定义了indegree入度数组

拓扑排序算法的参数只有一个

就是邻接表存储的AOV网

绿色这块代码做初始化

首先调用函数FindInDegree求出每个顶点的入度

教材上没有实现，前面我们单介绍过它的实现方法

随后初始化栈S，for循环，扫描所有顶点

如果它的入度为0，把它入栈

把计数器count置为0，count用来记录已经排序的顶点的个数

黄色这块，单循环就是刚才介绍的

拓扑排序的主要步骤，这里就不重复了

有count的自加，就是一个顶点排序以后，计数器加1

栈为空，单循环结束以后有两种情况

如果排序的顶点个数小于图的顶点个数

说明顶点没有被完全排序，意味着图中的存在环

返回error，如果不是这种情况

图中所有顶点都被排序，返回OK

好，同学们，拓扑排序的算法

我们就介绍到这儿，下次课再见