7.57.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,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6构造拓扑有序序列，即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。构造AOV网络全部顶点的拓扑有序序列的运算称为拓扑排序。如果通过拓扑排序能将如果通过拓扑排序能将AOVAOV网络的所有顶点都排入一个拓扑有序网络的所有顶点都排入一个拓扑有序的序列中的序列中,,则该网络中必定不会出现有向环。则该网络中必定不会出现有向环。如果如果AOVAOV网络中存在有向环，此网络中存在有向环，此AOVAOV网络所代表的工程是不可行的。网络所代表的工程是不可行的。拓扑排序方法拓扑排序方法④④重复以上重复以上②②、、③③步步,,直到直到全部顶点均已输出，全部顶点均已输出，拓扑有序序列形成，拓扑排序拓扑有序序列形成，拓扑排序完成；或完成；或图中还有未输出的顶点图中还有未输出的顶点,,但已跳出处理循环。但已跳出处理循环。说明图说明图中还剩下一些顶点中还剩下一些顶点,,它们都有直接前驱。这时网络中必它们都有直接前驱。这时网络中必存在有向环。存在有向环。①①输入输入AOVAOV网络；网络；②②在在AOVAOV网络中选一个网络中选一个没有直接前驱的顶点的顶点,,并输出之并输出之;;③③从图中删去该顶点从图中删去该顶点,,同时删去所有它发出的有向边同时删去所有它发出的有向边;;abhcdgfe得到的拓扑有序序列满足图中给出的所有前驱和后继关系。得到的拓扑有序序列满足图中给出的所有前驱和后继关系。如何在计算机上实现如何在计算机上实现对有向图的拓扑排序？对有向图的拓扑排序？在算法中需要用定量的描述替代定性的概念没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减1拓扑排序算法拓扑排序算法拓扑排序方法拓扑排序方法拓扑排序过程中涉及的数据和操作：拓扑排序过程中涉及的数据和操作：（（11）选择一入度为）选择一入度为00顶点顶点vv，，输出；输出；（（22））将将vv邻接到的顶点的入度减邻接到的顶点的入度减11；；（（33）重复（）重复（11）、（）、（22），直到输出全部顶），直到输出全部顶点，点，或，有向图没有入度为或，有向图没有入度为00的顶点。的顶点。数据：数据：有向图、顶点的入度；有向图、顶点的入度；操作：操作：（（11）选择一入度为）选择一入度为00顶点顶点vv，，输出；输出；（（22...
