有向无环图•无环的有向图称为有向无环图，简称无环的有向图称为有向无环图，简称DAGDAG图图•P179 P179 图图7.217.21：有向树、：有向树、DAGDAG图、有向图图、有向图•DAGDAG图可用于：图可用于： 描述含有公共子式的表达式；描述含有公共子式的表达式； 描述工程的进行过程；描述工程的进行过程；•有向无环图是描述一项工程进行过程的有有向无环图是描述一项工程进行过程的有效工具，主要进行拓扑排序和关键路径的效工具，主要进行拓扑排序和关键路径的操作 工程能否顺利进行工程能否顺利进行——拓扑排序拓扑排序 完成整个工程所需的最短时间完成整个工程所需的最短时间——关键路径关键路径 活动网络 (Activity Network)n n计划、施工过程、生产流程、程序流程等都计划、施工过程、生产流程、程序流程等都是是“工程工程”除了很小的工程外，一般都可除了很小的工程外，一般都可以将工程分为若干个称作以将工程分为若干个称作“活动活动”的子工程，的子工程，完成了这些活动，整个工程就可以完成了完成了这些活动，整个工程就可以完成了n n例：计算机专业学生的学习就是一个工程，例：计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一个活动，每一门课程的学习就是整个工程的一个活动，其中有些课程要求先修课程，有些则不要求，其中有些课程要求先修课程，有些则不要求，这样在有的课程之间就存在领先关系，而有这样在有的课程之间就存在领先关系，而有的课程则可以并行学习。
的课程则可以并行学习用顶点表示活动的网用顶点表示活动的网 (AOV-网网) C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1, C2 C4 数据结构数据结构 C3, C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译原理编译原理 C5, C4 C7 操作系统操作系统 C4, C9 C8 大学物理大学物理 C1 C9 计算机原理计算机原理 C8 学生课程学习工程图学生课程学习工程图C8C3C5C4C9C6C7C1C2 n n可以用可以用有向图有向图表示一个工程。
在这种有向表示一个工程在这种有向图中，图中，用顶点表示活动用顶点表示活动，，用有向边用有向边表示表示活动活动Vi 必须先于活动必须先于活动Vj 进行进行这种有向图称作顶点表示活动的向图称作顶点表示活动的AOV网网 (Activity On Vertex) n n在在AOV网络中不能出现有向回路网络中不能出现有向回路, 即有向即有向环如果出现了有向环，则意味着某项活环如果出现了有向环，则意味着某项活动应以自己作为先决条件动应以自己作为先决条件n n因此，对给定的因此，对给定的AOV网络，必须先判断它网络，必须先判断它是否存在有向环是否存在有向环 n n检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造网络构造它的拓扑有序序列即将各个顶点它的拓扑有序序列即将各个顶点 (代表各代表各个活动个活动)排列成一个线性有序的序列，使得排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系网络中所有应存在的前驱和后继关系都能得到满足都能得到满足 n n这种构造这种构造AOV网络全部顶点的拓扑有序序网络全部顶点的拓扑有序序列的运算就叫做拓扑排序列的运算就叫做拓扑排序。
n n如果通过拓扑排序能将如果通过拓扑排序能将AOV网络的所有顶网络的所有顶点都排入一个拓扑有序的序列中点都排入一个拓扑有序的序列中, 则该网络则该网络中中必定不会出现有向环必定不会出现有向环 n n如果如果AOV网络中存在有向环，此网络中存在有向环，此AOV网络网络所代表的工程是不可行的所代表的工程是不可行的n n例如例如, 对学生课程学习工程图进行拓扑排对学生课程学习工程图进行拓扑排序序, 得到的拓扑有序序列为得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6C7C1C2 拓扑排序的方法拓扑排序的方法①① 输入输入AOV网络，令网络，令 n 为顶点个数为顶点个数②② 在在AOV网络中选一个网络中选一个没有直接前驱没有直接前驱的顶点的顶点, 并输出之并输出之; ③③ 从图中删去该顶点从图中删去该顶点, 同时删去所有它发出同时删去所有它发出的有向边的有向边;④④ 重复以上重复以上 ②②、、③③步步, 直到直到F 全部顶点均已输出全部顶点均已输出，拓扑有序序列形成，，拓扑有序序列形成，拓扑排序完成；或拓扑排序完成；或F 图中还有未输出的顶点图中还有未输出的顶点, 但已跳出处理但已跳出处理循环循环。
说明图中还剩下一些顶点说明图中还剩下一些顶点, 它们都它们都有直接前驱这时网络中必存在有向环有直接前驱这时网络中必存在有向环 C0C1C2C3C4C5拓扑排序的过程拓扑排序的过程(a) 有向无环图有向无环图C2C5C1C0C3(b) 输出顶点输出顶点C4C1C2C5C3(c) 输出顶点输出顶点C0C4C0C2C5C1C3(d) 输出顶点输出顶点C3 C1C2C5(e) 输出顶点输出顶点C2C5C1(f) 输出顶点输出顶点C1C5(g) 输出顶点输出顶点C5 最后得到的拓扑有序序列为最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 它满足图中给出的所有前驱和后继关系，它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如对于本来没有这种关系的顶点，如C4和和C2，，也排也排出了先后次序关系出了先后次序关系h) 拓扑排序完成拓扑排序完成 AOV网络及其邻接表表示网络及其邻接表表示C0C1C2C3C4C5 C0 C1 C2 C3 0 C4 C5 0012345indegree data adj 130103 1 dest link 3 0 5 1 5 0 0 1 5 0 n n在在邻邻接接表表中中增增设设一一个个数数组组indegree[ ]，，记记录录各各顶顶点点入入度度。
入入度度为为零零的的顶顶点点即即无无前前驱驱顶点n n在在算算法法中中, 使使用用一一个个存存放放入入度度为为零零的的顶顶点点的栈的栈, 供选择和输出无前驱的顶点供选择和输出无前驱的顶点 拓扑排序算法可描述如下：拓扑排序算法可描述如下：uu建立入度为零的顶点栈建立入度为零的顶点栈;uu当入度为零的顶点栈不空时当入度为零的顶点栈不空时, 重复执行重复执行 ]] 从顶点栈中退出一个顶点从顶点栈中退出一个顶点, 并输出之并输出之;]] 从从AOV网络中删去这个顶点和它发网络中删去这个顶点和它发出的边出的边, 边的终顶点入度减一边的终顶点入度减一;]] 如果边的终顶点入度减至如果边的终顶点入度减至0, 则该顶点则该顶点进入度为零的顶点栈进入度为零的顶点栈;uu 如果输出顶点个数少于如果输出顶点个数少于AOV网络的顶点网络的顶点个数个数, 则报告网络中存在有向环则报告网络中存在有向环uuP182算法算法7.12 用边表示活动的网络用边表示活动的网络(AOE网网)n n如果在带权的有向无环图中如果在带权的有向无环图中, 用有向边表示用有向边表示一个工程中的活动一个工程中的活动 (Activity), 用边上权用边上权值表示活动持续时间值表示活动持续时间 (Duration), 用顶点用顶点表示事件表示事件 (Event), 则这样的有向图叫做用则这样的有向图叫做用边表示活动的网络边表示活动的网络, 简称简称 AOE ( Activity On Edges ) 网。
网n nAOE网在某些工程进度估算方面非常有用网在某些工程进度估算方面非常有用例如，可以使人们了解：例如，可以使人们了解：uu完成整个工程至少需要多少时间完成整个工程至少需要多少时间(假设网假设网络中没有环络中没有环)? uu为缩短完成工程所需的时间为缩短完成工程所需的时间, 应当加快哪应当加快哪些活动些活动? n n从源点到各个顶点从源点到各个顶点, 以及从源点到汇点的有以及从源点到汇点的有向路径可能不止一条，这些路径的长度也可向路径可能不止一条，这些路径的长度也可能不同，完成不同路径的活动所需的时间虽能不同，完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成然不同，但只有各条路径上所有活动都完成了了, 整个工程才能完成整个工程才能完成n n因此因此, 完成整个工程所需的时间取决于从源完成整个工程所需的时间取决于从源点到汇点的最长路径长度点到汇点的最长路径长度, 即在这条路径上即在这条路径上所有活动的持续时间之和所有活动的持续时间之和这条路径长度最这条路径长度最长的路径叫做长的路径叫做关键路径关键路径(Critical Path) a9=61324a1=8a2=125678a10=12a8=18a5=28a6=8a7=6a3=14a4=10n n要找出关键路径，必须找出要找出关键路径，必须找出关键活动关键活动, 即不即不按期完成就会影响整个工程完成的活动。
按期完成就会影响整个工程完成的活动n n关键路径上的所有活动都是关键活动关键路径上的所有活动都是关键活动因此此, 只要找到了关键活动只要找到了关键活动, 就可以找到关键就可以找到关键路径例如路径例如, 下图就是一个下图就是一个AOE网 定义几个与计算关键活动有关的量：定义几个与计算关键活动有关的量：①① 事件事件Vi 的最早发生时间的最早发生时间ve(i) 是从是从源点源点V0 到到顶点顶点Vi 的最长路径长度的最长路径长度②② 事件事件Vi 的最迟发生时间的最迟发生时间vl[i] 是是在在保保证证汇汇点点Vn-1 在在ve[n-1] 时时刻刻完完成成（（即即不不影影响响整整个个工工程程工工期期））的的前前提提下下，，事事件件Vi 允许的最迟开始时间允许的最迟开始时间③③ 活动活动ak 的最早可能开始时间的最早可能开始时间 e[k] 设设活活动动ak 在在弧弧< Vi , Vj >上上, 则则e[k]是是从从源源点点V0到顶点到顶点Vi 的最长路径长度因此的最长路径长度因此, e[k] = ve[i] ④④ 活动活动ak 的最迟允许开始时间的最迟允许开始时间 l[k] 在不会引起整个工程时间延误的前提下在不会引起整个工程时间延误的前提下, 该该活动允许的最迟开始时间。
活动允许的最迟开始时间 l[k] = vl[j] - dur() 其中其中, dur()是完成是完成 ak 所需的时间所需的时间⑤⑤ 时间余量时间余量 l[k] - e[k] 表示活动表示活动 ak 的最早可能开始时间和最迟允的最早可能开始时间和最迟允许开始时间的时间余量许开始时间的时间余量l[k] == e[k] 表示活表示活动动 ak 是没有时间余量的关键活动是没有时间余量的关键活动n n为找出关键活动为找出关键活动, 需要求出各个活动的需要求出各个活动的 e[k] 与与 l[k]，，以判别是否以判别是否 l[k] == e[k] n n为求得为求得 e[k]与与 l[k], 需要先求得从源点需要先求得从源点 V0 到各到各个顶点个顶点 Vi 的的 ve[i] 和和 vl[i]n n求求ve[i]和和vl[i]的递推公式的递推公式uu 从从 ve[0] = 0 开始，向前递推开始，向前递推 < Vj, Vi > S2, i = 1, 2, , n-1 S2 是所有指向是所有指向Vi 的有向边的有向边< Vj , Vi >的集合。
的集合uu 从从vl[n-1] = ve[n-1]开始，反向递推开始，反向递推 < Vi, Vj > S1, i = n-2, n-3, , 0S1是所有源自是所有源自Vi的有向边的有向边< Vi , Vj >的集合 n n这两个递推公式的计算必须分别在这两个递推公式的计算必须分别在拓扑有序拓扑有序及及逆拓扑有序逆拓扑有序的前提下进行的前提下进行n n设设活动活动ak (k=1,2,…,e)在带权有向边在带权有向边< Vi , Vj > 上上, 其持续时间用其持续时间用dur () 表示表示, 则则有有 e[k] = ve[i]；； l[k] = vl[j] - dur()；；k = 1, 2, …, e这样就得到计算关键路径的算法这样就得到计算关键路径的算法为了简化算法为了简化算法, 假定在求关键路径之前已经假定在求关键路径之前已经对各顶点实现了拓扑排序对各顶点实现了拓扑排序, 并按拓扑有序的并按拓扑有序的顺序对各顶点重新进行了编号顺序对各顶点重新进行了编号 对算法对算法7.12作如下修改得算法作如下修改得算法7.13：： （算法（算法7.13求各事件的求各事件的ve）） ①① 设初值设初值ve(i)=0 (0≤≤ i≤≤ n-1) ②② 计算计算Vj的直接后继的直接后继Vk的的ve(k)：： 若若ve(j)+dut() > ve(k) 则则ve(k)=ve(j)+ dut() ③③ 为求为求vl，，设一栈记录拓扑有序序列，之后设一栈记录拓扑有序序列，之后弹栈求逆拓扑有序序列弹栈求逆拓扑有序序列算法算法7.14 （先求各事件的（先求各事件的vl，，再求各活动的再求各活动的e和和l（（7.14中用中用ee和和el表示），当某个活动的表示），当某个活动的e=l，，则该则该活动是关键活动）活动是关键活动） 1324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10VeVl1 2 3 4 5 6 7 8 0 8 12 22 28 40 46 58 0 8 12 22 28 40 46 58el0 0 8 12 12 22 22 28 40 460 0 8 12 12 32 22 28 40 461 2 3 4 5 6 7 8 9 10三条三条三条三条关键路径：关键路径：关键路径：关键路径：1-2-4-5-7-81-2-4-5-7-81-3-4-5-7-8 1-3-6-7-81-3-4-5-7-8 1-3-6-7-8 注意注意ØØ所有顶点按拓扑有序的次序编号所有顶点按拓扑有序的次序编号ØØ仅计算仅计算 ve[i] 和和 vl[i] 是不够的，还须计算是不够的，还须计算 e[k] 和和 l[k]。
ØØ不是任一关键活动加速一定能使整个工程不是任一关键活动加速一定能使整个工程提前ØØ想使整个工程提前，要考虑各条关键路径想使整个工程提前，要考虑各条关键路径上所有关键活动上所有关键活动。