有向无环图:无环的有向图,简称 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的前面,具有这种性质的线性序列称为拓扑有序序列,相应的拓扑有序排序的算法称为拓扑排序。
注意:
1、若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。
2、若图中存在有向环,则不可能使顶点满足拓扑次序。
3、一个DAG可能存在多个拓扑序列。
检测 AOV 网中是否存在环方法:
DFS(深度优先搜索),出现返回边则有环;拓扑排序,若所有的顶点都出现在拓扑排序中,则不出现环。如果使用 DFS 进行拓扑排序,那么结果是逆向的拓扑排序有序序列。
拓扑排序方法:
1)在有向图中选一个无前趋的顶点v,输出之;
2)从有向图中删除v及以v为尾的弧;
3)重复1)、2),直接全部输出全部顶点或有向图中不存在无前趋的结点时为止。
删除 v2,v3,v4,v5,v6以及以他们为尾部的弧
注意:一个AOV网的拓扑序列不是唯一的
辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4404004.html