5有向无环图及应用有向无环图及应用一一AOV-AOV-网网二二AOV-AOV-网与拓扑排序网与拓扑排序三三AOE-AOE-网与关键路径网与关键路径有向无环图及应用有向无环图的定义有向图中是否有环的检查有向无环图的应用:工程能否顺利进行——拓扑排序估算完成工程的最短时间——关键路径有向无环图有向无环图有向无环图（有向无环图（DAGDAG图）：图）：没有回路没有回路((环环))的有向图
有向无环图有向无环图有向图（有环）有向图（有环）一、一、AOV-AOV-网网((ActivityOnVertices)ActivityOnVertices)表示工程的有向图中，用顶点表示活动，用有向边表示活动Vi必须先于活动Vj进行
这种有向图叫做顶点表示活动的AOV网络
（用顶点表示活动，弧表示活动间的优先关系的有向图）在AOV网络中不能出现有向回路（即有向环）
若出现了有向环，则意味着某项活动应以自己作为先决条件
因此，对给定的AOV网络，必须先判断它是否存在有向环
检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序
何谓“拓扑排序”
对有向图进行如下操作:按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系
由此所得顶点的线性序列称之为拓扑有序序列
拓扑排序是对有向无环图的顶点的一种排序
拓扑排序举例课程编号课程名称先修课程C1高等数学无C2程序设计基础无C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C8表示教学计划（课程之间）的优先关系有向图C8C8C3C3C5C5C4C4C9C9C6C6C7C7C1C1C2C2对图进行拓扑排序,得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,
