图的应用--拓扑排序
有向无环图的应用
AOV网:
AOE网:
什么是拓扑排序
排课表
上面的就是一个AOV网
AOV网的特点
-
若从i到j有一条路径,则i是j的前驱;j是i的后继.
-
若<i,j>是网中有向边,则i是j的直接前驱;j是i的直接后继.
-
在AOV网中不允许有回路,因为如果有回路存在,这表明某项活动以自己为先决条件,显然这是荒谬的.
如何判断AOV网中是否存在回路?
拓扑排序
拓扑排序的方法
- 选一个没有前驱的顶点且输出之.
- 从图中删除该顶点和所有以他为尾的弧.
- 重复上述两步,直至全部的顶点均已输出;
或者当图不存在无前驱的顶点为止
一个AOV网的拓扑序列是不唯一的
拓扑排序的重要应用
对于有向图构造顶点的拓扑有序序列,若网中所有顶点都在它的拓扑序列中,这该AOV网必定不存在环.
存在环的时候删不掉
