有向无环图:无环的有向图,简称 DAG (Directed Acycline Graph) 图。
一个有向图的生成树是一个有向树,一个非连通有向图的若干强连通分量生成若干有向树,这些有向数形成生成森林。
在工程计划和管理方面的应用
除最简单的情况之外,几乎所有的工程都可分为若干个称作“活动”的子工程,并且这些子工程之间通常受着一定条件的约束,例如:其中某些子工程必须在另一些子工
程完成之后才能开始。对整个工程和系统,人们关心的是两方面的问题:
一是工程能否顺利进行,即工程流程是否“合理”;
二是完成整个工程所必须的最短时间。
对应到有向图即为进行拓扑排序(AOV网)和求关键路径(AOE网)。
拓扑排序
AOV 网:用一个有向图表示一个工程的各子工程及其相互制约的关系,其中以顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV (Activity On Vertex network)网。
比如、某工程可分为7个子工程(V0、V1、V2、V3、V4、V5、V6),若用顶点表示子工程(也称活动),用弧表示子工程间的顺序关系,工程流程可用如下的AOV网表示。
比如排课表
AOV 网的特点:若从 i 到 j 有一条有向路径,则 i是 j 的前驱;j 是 i 的后继。若 < i , j > 是网中有向边,则 i 是 j 的直接前驱; j 是 i 的直接后继。AOV 网中不允许有回路,因为如果有回路存在,则表明某项活动以自己为先决条件,显然这是荒谬的。
问题:如何判别 AOV 网中是否存在回路?即如何AOV网表示的工程能顺利进行?合理?
拓扑排序:
在 AOV 网没有回路的前提下,我们将全部活动排列成一个线性序,使得若 AOV 网中有弧 <i, j> 存在,则在这个序列中, i 一定排在 j的前面,具有这种性质的线性序列称为拓扑有序序列,相应的拓扑有序排序的算法称为拓扑排序。
注意:
检测 AOV 网中是否存在环方法:
3)重复1)、2),直接全部输出全部顶点或有向图中不存在无前趋的结点时为止。
删除 v2,v3,v4,v5,v6以及以他们为尾部的弧
注意:一个AOV网的拓扑序列不是唯一的