6-7 有向无环图及其应用

有向无环图

有向无环图：无环的有向图，简称DAG图（Directed Acycline Graph）

AOV网：拓扑排序

• 用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网（Activity On Vertex Network）

AOE网：关键路径

• 用一个有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网（Activity On Edge）

AOV网的特点

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

拓扑排序的方法

• 在有向图中选一个没有前驱的顶点且输出之
• 从图中删除该顶点和所有以它为尾的弧
• 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止

检测AOV网中是否存在环：

对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。（若存在环，代表一个顶点有前驱顶点，不会被加入到AOV网中）