拓扑排序与关键路径

1、关于拓扑排序和关键路径第一张，PPT共三十二页，创作于2022年6月AOV-网 用顶点表示活动，用边来表示活动之间的先后关系的有向图称为顶点活动网，简称AOV-网。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。7.5.1 拓扑排序第二张，PPT共三十二页，创作于2022年6月 C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普

2、通物理 C1 C9 计算机原理 C8 课程代号 课程名称 先修课程第三张，PPT共三十二页，创作于2022年6月学生课程学习工程图C8C3C5C4C9C6C7C1C2第四张，PPT共三十二页，创作于2022年6月在AOV网络中不能出现回路, 即环。如果出现了环，则意味着某项活动应以自己作为先决条件，这是荒谬的。因此，对给定的AOV网络，必须先判断它是否存在有向环。第五张，PPT共三十二页，创作于2022年6月检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。 这种构造AOV网全

3、部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中, 则该网络中必定不会出现有向环。第六张，PPT共三十二页，创作于2022年6月如果AOV网络中存在环，此AOV网络所代表的工程是不可行的。例如, 对学生选课工程图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6C7C1C2第七张，PPT共三十二页，创作于2022年6月拓扑排序的方法 输入AOV网络。令

4、n 为顶点个数。 在AOV网络中选一个没有直接前驱的顶点, 并输出之; 从图中删去该顶点, 同时删去所有它发出的有向边; 重复以上 、步, 直到 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或 图中还有未输出的顶点, 但已跳出处理循环。说明图中还剩下一些顶点, 它们都有直接前驱。这时网络中必存在有向环。第八张，PPT共三十二页，创作于2022年6月C0C1C4C3C2C5拓扑排序的过程(a) 有向无环图C4C5C1C0C3(b) 输出顶点C2C1C4C5C3(c) 输出顶点C0C2C0C4C5C1C3(d) 输出顶点C3第九张，PPT共三十二页，创作于2022年6月C1C4C5(e) 输

5、出顶点C4C5C1(f) 输出顶点C1C5(g) 输出顶点C5 最后得到的拓扑有序序列为 C2 , C0 , C3 , C4 , C1 , C5 。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C2和C4，也排出了先后次序关系。(h) 拓扑排序完成第十张，PPT共三十二页，创作于2022年6月AOV网络及其邻接表表示C0C1C4C3C2C5 C0 C1 C2 C3 0 C4 C5 0012345indegree data firstarc 130103 1adjvex nextarc 3 0 5 0 1 5 0 0 1 5 0第十一张，PPT共三十二页，创作于2022年6月

6、在邻接表中增设一个数组indegree ，记录各顶点入度。在拓扑排序前前,初始化入度数组。入度为零的顶点即无前驱顶点。在算法中, 使用栈存放入度为零的顶点, 供选择和输出无前驱的顶点。第十二张，PPT共三十二页，创作于2022年6月拓扑排序算法可描述如下：入度为零的顶点入栈;当栈不空时, 重复执行 从顶点栈中退出一个顶点, 并输出之; 从AOV网络中删去这个顶点和它发出的边, 边的终顶点入度减一; 如果边的终顶点入度减至0, 则该顶点进栈; 如果输出顶点个数少于AOV网络的顶点个数, 则报告网络中存在有向环。第十三张，PPT共三十二页，创作于2022年6月拓扑排序的算法void Topolog

7、icalSort (ALGraph G) FindInDegree(G,indegree); /初始化indegree InitStack(S); for (i = 0; i G.vexnum; i+ ) /入度为零的顶点 if (indegreei = 0 ) Push(S, i); /进栈 count=0; /对输出顶点计数 第十四张，PPT共三十二页，创作于2022年6月 while( ! StackEmpty(S) ) Pop( S, i ); /退栈 cout i nextarc) k = p-adjvex; if ( -indegreek = 0 ) /顶点入度减1 Push( S

8、, k ); /顶点的入度减至零, 进栈 第十五张，PPT共三十二页，创作于2022年6月7.5.2 关键路径一、AOE网如果在有向无环图中, 用有向边表示一个工程中的活动 (Activity), 用边上权值表示活动持续时间 (Duration), 用顶点表示事件 , 则这样的有向图叫做用边表示活动的网络, 简称 AOE ( Activity On Edges ) 网。第十六张，PPT共三十二页，创作于2022年6月AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：完成整个工程至少需要多少时间(假设网络中没有环)? 为缩短完成工程所需的时间, 应当加快哪些活动?第十七张，PPT共三十

9、二页，创作于2022年6月从源点到汇点的路径可能不止一条，并且这些路径的长度也可能不同。 完成不同路径的活动所需的时间虽然不同, 但只有各条路径上所有活动都完成了, 整个工程才算完成。因此, 完成整个工程所需的时间取决于从源点到汇点的最长路径长度, 即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。第十八张，PPT共三十二页，创作于2022年6月要找出关键路径，必须找出关键活动, 即不按期完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。因此, 只要找到了关键活动, 就可以找到关键路径。例如, 下图就是一个AOE网。V1V

10、3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1第十九张，PPT共三十二页，创作于2022年6月二、相关术语 事件Vi 的最早发生时间ve(i) 是从源点V0 到顶点Vi 的最长路径长度。 事件Vi 的最迟发生时间vl(i) 在不推迟整个工程完成的前提下，事件Vi 的最迟发生时间。 活动ai 的最早开始时间 e(i) 活动ai 的最迟开始时间 l(i) 表示在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的事件。第二十张，PPT共三十二页，创作于2022年6月 时间余量 l(i) e(i) 表示活动 ai 的最早可能开始时间和最迟允许开始时间的时间余量。

11、 l(i) = e(i) 的活动称为关键活动。第二十一张，PPT共三十二页，创作于2022年6月三、怎样求关键路径？ 如何找e(i)=l(i)的关键活动？为找出关键活动, 需要求各个活动的 e(i) 与 l(i)，以判别是否 l(i) = e(i)。 设活动ai由弧表示， 且活动持续时间记为dut(), 则 e(i) = ve(j) l(i) = vl(k) - dut()VjVkai第二十二张，PPT共三十二页，创作于2022年6月 如何求ve(i)和vl(i)？求ve(i)的递推公式 从 ve(0)= 0 开始，向前递推 T, i = 1, 2, , n-1 T 是所有以第j个顶点为头的弧

12、的集合。例，求右图中顶点V6的最早发生时间。V3V4V5V6a6=3a7=2a8=1266第二十三张，PPT共三十二页，创作于2022年6月V1V2V3V4V5V6顶点 ve vl032668V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1032668第二十四张，PPT共三十二页，创作于2022年6月求vl(i)的递推公式 从vl(n-1) = ve(n-1)开始，反向递推 S, i = n-2, n-3, , 0S是所有以第i个顶点为尾的弧的集合。 例，求右图中顶点V1的最迟发生时间。V1V3V2a1=3a2=224第二十五张，PPT共三十二页，创作于

13、2022年6月V1V2V3V4V5V6顶点 ve vl032668V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1042678042678第二十六张，PPT共三十二页，创作于2022年6月a1a2a3a4a5a6a7a8活动 e l l-e011000341220253660671341V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1V1V2V3V4V5V6顶点 ve vl032668042678第二十七张，PPT共三十二页，创作于2022年6月四、算法实现实现步骤：输入e条弧，建立AOE-网的存储结构；从源点v0

14、出发，令ve0=0，按拓扑有序求其余各顶点的最早发生时间vei（1in-1）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤。从汇点vn出发，令vln-1=ven-1，按逆拓扑有序求其余各顶点的最迟发生时间vli（n-2i2）；根据各顶点的ve和vl的值，求每条弧s的最早发生时间e(s)和最迟发生时间l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。第二十八张，PPT共三十二页，创作于2022年6月 算法实现Status TopologicalOrder(ALGraph G,Stack &T) /求各顶点事件的最早发生时间v

15、e（全局变量），T为拓扑序列顶点栈 FindInDegree(G,indegree)； /对各顶点求入度 InitStack(T)；count=0； ve0.G.vexnum-1=0； /初始化 while(!StackEmpty(S) /S为零入度顶点栈 Pop(S,j)； push(T,j)； +count； /j号顶点入T栈并计数 for(p=G.verticesj.firstarc； p； p=pnextarc) k=padjvex； /对j号顶点的每个邻接点的入度减1 if(-indegreek=0) push(S,k)； if(vej+*(pinfo)vek) vek=vej+*(

16、pinfo)； if(countG.vexnum) return ERROR； /该有向网有回路 else return OK；第二十九张，PPT共三十二页，创作于2022年6月Status CriticalPath(ALGraph G) /G为有向网，输出G的各项关键活动 if(!TopologicalOrder(G,T) return ERROR; vl0.G.vexnum-1=ve0.G.vexnum-1;/初始化顶点事件的最迟发生时间 while(!StackEmpty(T) /按逆拓扑有序求各顶点的vl值 for(pop(T,j),p=G.verticesj.firstarc；p；p=pnextarc) k=padjvex； dut=*(pinfo)； if(vlk-dutvlj) vlj=vlk-dut； for(j=0；jG.vexnum；+j) /求ee，el和关键活动 for(p=G.verticesj；p；p=pnextarc) k=pa