有向无环图的应用—AOV网 和 拓扑排序

时间:2023-06-20 17:20:26

有向无环图:无环的有向图,简称 DAG (Directed Acycline Graph) 图。

有向无环图的应用—AOV网 和 拓扑排序

一个有向图的生成树是一个有向树,一个非连通有向图的若干强连通分量生成若干有向树,这些有向数形成生成森林。

在工程计划和管理方面的应用

除最简单的情况之外,几乎所有的工程都可分为若干个称作“活动”的子工程,并且这些子工程之间通常受着一定条件的约束,例如:其中某些子工程必须在另一些子工

程完成之后才能开始。对整个工程和系统,人们关心的是两方面的问题:

一是工程能否顺利进行,即工程流程是否“合理”;

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

对应到有向图即为进行拓扑排序(AOV网)和求关键路径(AOE网)。

拓扑排序

AOV 网:用一个有向图表示一个工程的各子工程及其相互制约的关系,其中以顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV (Activity On  Vertex network)网。

比如、某工程可分为7个子工程(V0、V1、V2、V3、V4、V5、V6),若用顶点表示子工程(也称活动),用弧表示子工程间的顺序关系,工程流程可用如下的AOV网表示。

有向无环图的应用—AOV网 和 拓扑排序

比如排课表

有向无环图的应用—AOV网 和 拓扑排序

有向无环图的应用—AOV网 和 拓扑排序

AOV 网的特点:若从 i 到 j 有一条有向路径,则 i是 j 的前驱;j 是 i 的后继。若 < i , j > 是网中有向边,则 i 是 j 的直接前驱; j 是 i 的直接后继。AOV 网中不允许有回路,因为如果有回路存在,则表明某项活动以自己为先决条件,显然这是荒谬的。

问题:如何判别 AOV 网中是否存在回路?即如何AOV网表示的工程能顺利进行?合理?

拓扑排序:

在 AOV 网没有回路的前提下,我们将全部活动排列成一个线性序,使得若 AOV 网中有弧 <i,  j> 存在,则在这个序列中, i  一定排在  j的前面,具有这种性质的线性序列称为拓扑有序序列,相应的拓扑有序排序的算法称为拓扑排序。

注意:

1、若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。
2、若图中存在有向环,则不可能使顶点满足拓扑次序。
3、一个DAG可能存在多个拓扑序列。

检测 AOV 网中是否存在环方法:

DFS(深度优先搜索),出现返回边则有环;拓扑排序,若所有的顶点都出现在拓扑排序中,则不出现环。如果使用 DFS 进行拓扑排序,那么结果是逆向的拓扑排序有序序列。 
拓扑排序方法:
有向无环图的应用—AOV网 和 拓扑排序
1)在有向图中选一个无前趋的顶点v,输出之;
2)从有向图中删除v及以v为尾的弧;
有向无环图的应用—AOV网 和 拓扑排序

3)重复1)、2),直接全部输出全部顶点或有向图中不存在无前趋的结点时为止。

有向无环图的应用—AOV网 和 拓扑排序

删除 v2,v3,v4,v5,v6以及以他们为尾部的弧

有向无环图的应用—AOV网 和 拓扑排序

注意:一个AOV网的拓扑序列不是唯一的