拓扑排序和关键路径

1、7.5有向无环图及其应用，有向无环图：没有环的有向图，简称DAG图。有向无环图的实际应用有向无环图是描述工程或系统进展的有效工具。对于整个项目和系统，人们最关心的是两个方面：(1)项目能否顺利进行；(2)项目完成所需的最短时间。它归结为有向图，这是排序拓扑和求解关键路径的问题。AOV网用顶点来表示活动，用边来表示活动之间的顺序关系的有向图叫做顶点网上的活动，简称AOV网。例如，计算机专业的学习是一个项目，而每门课程的学习是整个项目的一些活动。其中一些课程需要先修，而另一些则不需要。这样，有些课程之间就有了主导关系，有些课程可以并行学习。7.5.1拓扑排序，C1高等数学C2程序设计基础C3离散数

2、学C1，C2C4数据结构C3，C2C5高级语言程序设计C2C6编译方法C5，C4C7操作系统C4，C9C8普通物理C1C9计算机原理C8，课程代码课程名称必修课，学生课程学习工程制图，C8，C3，C5，C4，C9如果有一个环，它意味着一个活动应该以自己为前提，这是荒谬的。因此，对于给定的AOV网络，我们必须首先判断它是否有一个有向循环。检测有向环的一种方法是为AOV网络构造其拓扑有序序列。也就是说，每一个顶点(代表每一个活动)被安排成一个线性和有序的序列，以便可以满足AOV网络中应该存在的所有先行关系和后继关系。这种构造AOV网络所有顶点的拓扑有序序列的操作称为拓扑排序。如果AOV网络的所有顶

3、点都可以通过拓扑排序排列成一个拓扑有序序列，那么有向环就不会出现在网络中。如果AOV网络中有一个环，这个AOV网络所代表的项目是不可行的。例如，学生选修课工程制图的拓扑顺序是C1、C2、C3、C4、C5、C6、C8、C9、C7或C1、C8、C9、C2、C5、C3、C4、C7、C6、C8、C3、C5、C4、C9、C6，设n为顶点数。在AOV网络中选择一个没有直接前驱的顶点并输出；从图中删除顶点，并删除它发出的所有有向边；重复上述步骤，直到所有顶点都已输出，形成拓扑有序序列，拓扑排序完成；或者，图中有些顶点尚未输出，但它们已经跳出了处理循环。解释图中还有一些顶点，它们都有直接的前兆。此时，网络中必

4、须有一个定向环。，C0，C1，C4，C3，C2，C5，拓扑排序过程，(a)有向无环图，C4，C5，C1，C0，C3，(b)输出顶点C2 (e)输出顶点C4，C5，C1，(f)输出顶点C1，C5，和(g)输出顶点C5，最后拓扑排序序列是C2，C0，C3，C4，C1，C5。它满足图中给出的所有先行关系和后继关系，并且还排除了不具有这种关系的顶点的优先关系，例如C2和C4。(h)拓扑排序完成，AOV网络及其邻居表表明，C0、C1、C4、C3、C2、C5、C0C1C2C30C4C50、012345、Indegreedatafirstarc、130103、在拓扑排序前初始化入度数组。穿透为零的顶点是没有前驱的顶点。在该算法中，堆栈用于存储具有零度入口的顶点，以选择和输出没有前驱的顶点。拓扑排序算法可以描述如下：(1)具有零度入口的顶点被堆叠；当堆栈不为空时，重复执行以从顶点堆栈中退出一个顶点并输出它；从AOV网络中删除该顶点及其边，并将边的最终顶点穿透减少1；如果边的最终顶点穿透减少到0，则顶点被堆叠；如果输出顶点的数量少于AOV网络，则