拓扑排序和关键路径.ppt

《拓扑排序和关键路径.ppt》由会员分享，可在线阅读，更多相关《拓扑排序和关键路径.ppt（49页珍藏版）》请在三一办公上搜索。

1、1,Essential of Lecture Sixteen：,一、拓扑排序 二、关键路径,第十六讲,2,一、有向无环图及其应用,有向无环图：没有回路的有向图,（a）有向树（b）有向无环图（c）有向图,问题：判断一个有向图是否为有向无环图的方法是？,3,一、有向无环图及其应用,应用：工程流程、生产过程中各道工序的流程、程序流程、课程的流程。对整个工程和系统，人们关心的问题是：（1）工程能否顺利进行,，即工程流程是否“合理”；（2）完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键子工程。,（1）拓扑排序（2）关键路径,4,一、有向无环图及其应用,AOV网(activity on ve

2、rtex network)用顶点表示活动，边表示活动的顺序关系。,为求解工程流程是否“合理”，通常用AOV网的有向图表示工程流程。,1、拓扑排序,5,某工程可分为6个子工程，若用顶点表示子工程（也称活动）,用弧表示子工程间的顺序关系。工程流程可用如下AOV网表示：,例,一、有向无环图及其应用,6,一、有向无环图及其应用,例 2:计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。,例,7,例 2:课程流程图,8,一个可行的施工计划为：A,B,C,D,E,F 一个可行的学习计划为：

3、C1,C9,C4,C2,C10,C11,C12,C3,C6,C5,C7,C8 可行的计划的特点：若在流程图中顶点v是顶点u 的前趋，则在计划序列中顶点v 也是u的前趋。,一、有向无环图及其应用,9,一、有向无环图及其应用,拓扑排序(TopologicalSort),按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系,由此所得顶点的线性序列称之为拓扑有序序列,10,例如：对于下列有向图,可求得拓扑有序序列：A B C D 或 A C B D,11,B,D,A,C,反之，对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个

4、回路 B,C,D,12,一、有向无环图及其应用,拓扑排序方法：第一步：在有向图选一无前趋的顶点v，输出；第二步：从有向图中删除v及以v为尾的孤；重复第一步和第二步，直到输出全部顶点或有向图中不存在无前趋顶点（此时图中存在环）。,13,拓扑序列：开始,（0）,14,15,16,（7）,17,18,拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一个AOV网的拓扑序列不是唯一的,19,a,b,c,g,h,d,f,e,a,b,h,c,d,g,f,e,20,一、有向无环图及其应用,（

5、1）选择一入度为 0 顶点 v，输出；（2）将 v 邻接到的顶点的入度减1；（3）重复12，直到输出全部顶点或图中没有入度为0的顶点；拓扑排序涉及的数据和操作：数据：有向图，顶点的入度；操作：（1）选择一入度为 0 顶点v，输出；（2）将 v 邻接到的顶点 u 的入度减1；,拓扑排序算法,21,设计数据结构,1.图的存储结构：采用邻接表存储，在顶点表中增加一个入度域。顶点表结点,2.栈S：存储所有无前驱的顶点。思考：可以用队列吗？,AOV网应用：拓扑排序,22,(a)一个AOV网(b)AOV网的邻接表存储,012345,in vertex firstarc,3 A 0 B1 C3 D0 E2

6、F,0,3,0,0,5,2,3,3,5,拓扑排序,AOV网应用：拓扑排序,23,拓扑排序,012345,in vertex firstarc,3 A 0 B 1 C 3 D 0 E 2 F,0,3,0,0,5,2,3,3,5,B,E,AOV网应用：拓扑排序,24,拓扑排序,012345,in vertex firstarc,3 A 0 B 1 C 3 D 0 E 2 F,0,3,0,0,5,2,3,3,5,B,E,0,C,2,1,AOV网应用：拓扑排序,25,拓扑排序,012345,in vertex firstarc,3 A 0 B 0 C 2 D 0 E 1 F,0,3,0,0,5,2,3

7、,3,5,B,C,2,1,AOV网应用：拓扑排序,26,拓扑排序,012345,in vertex firstarc,2 A 0 B 0 C 1 D 0 E 1 F,0,3,0,0,5,2,3,3,5,B,D,0,1,AOV网应用：拓扑排序,27,拓扑排序,012345,in vertex firstarc,1 A 0 B 0 C 0 D 0 E 1 F,0,3,0,0,5,2,3,3,5,0,0,A,F,AOV网应用：拓扑排序,28,拓扑排序,012345,in vertex firstarc,0 A 0 B 0 C 0 D 0 E 0 F,0,3,0,0,5,2,3,3,5,A,F,AOV

8、网应用：拓扑排序,29,1.栈或队列S初始化；累加器count初始化；2.扫描顶点表，将没有前驱的顶点压栈或入队；3.当栈或队列S非空时循环 3.1 退出vj栈顶或队首元素；输出vj；累加器加1 3.2 将顶点vj的各个邻接点的入度减1；3.3 将新的入度为0的顶点入栈或入队；4.if(countvertexNum)输出有回路信息；,拓扑排序算法伪代码,AOV网应用：拓扑排序,作业:请编程求AOV网的拓扑排序。,30,template StatusCode TopSort(const AdjMatrixDirGraph/建立入度为0的顶点队列,31,while(!q.Empty()/队列非空i

9、nt v1;q.OutQueue(v1);/取出一个入度为0的顶点cout v1;count+;/对输出顶点进行记数for(int v2=g.FirstAdjVex(v1);v2!=-1;v2=g.NextAdjVex(v1,v2)/v2为v1的一个邻接点if(-indegreev2=0)/邻接点入度减1 q.InQueue(v2);/入度为0,v2入队;delete indegree;/释放indegree所占用的存储空间if(count g.GetVexNum()return FAIL;/g有回路else return SUCCESS;/拓扑排序成功,32,一、有向无环图及其应用,2、关键

10、路径,AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。,AOE网的性质：只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。,33,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,例如:,整个工程完成的时间为：从有向图的始点到终点的最长路径,始点,终点,6,1,7,4,34,顶点表示事件,边表示活动,事件Vj发生表

11、示 ak已结束,事件Vi发生表示 ak可以开始,AOE网,一、有向无环图及其应用,35,一、有向无环图及其应用,AOE网可以回答下列问题：1.完成整个工程至少需要多少时间?2.为缩短完成工程所需的时间,应当加快哪些活动?,从始点到终点的路径可能不止一条，只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的最短时间取决于从始点到终点的最长路径长度，即这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径。,36,一、有向无环图及其应用,事件Vj 的最早发生时间Vej，是从源点到顶点Vj的最大路径长度。事件Vj 的最迟发生时间Vlj，指在不推迟整个工期的前提下

12、，事件最晚必须发生的时间。活动ak的最早开始时间ek，该活动的尾事件的最早发生时间。活动ak的最晚开始时间lk，它的弧头顶点事件允许的最晚发生时间减去该活动持续的时间。活动ak 的时间余量diffk=lk-ek时间余量为0者即为关键活动,37,vek是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。,ve1=0vek=maxvej+len(pk)pk表示所有到达vk的有向边的集合,事件的最早发生时间vek,AOE网应用：关键路径,38,vek,0,6,4,5,7,7,16,14,18,vek=maxvej+len,AOE网应用：关键路径,39,v

13、lk是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。,事件的最迟发生时间vlk,vlk=minvlj-len（sk）sk为所有从vk发出的有向边的集合,AOE网应用：关键路径,40,vek,vlk,0,6,4,5,7,7,16,14,18,18,14,16,10,7,8,6,6,0,vlk=minvlj-len,AOE网应用：关键路径,41,活动的最早开始时间ei,若活动ai是由弧表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有：ei=vek,AOE网应用：关键路径,42,vek,0,6,4,5,7,7,16,14,18,a2,a7,a6,a5,a4,a1,a3,

14、a9,a8,ei,0,0,0,6,4,5,7,7,7,a10,a11,16,14,ei=vek,AOE网应用：关键路径,43,活动ai的最晚开始时间是指，在不推迟整个工期的前提下，ai必须开始的最晚时间。若ai由弧表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，有：li=vlj-len,活动的最晚开始时间li,vlk,18,14,16,10,7,8,6,6,0,AOE网应用：关键路径,44,li,10,7,7,8,6,6,3,2,0,16,14,a2,a7,a6,a5,a4,a1,a3,a9,a8,a10,a11,vlk,18,14,16,10,7,8,6,6,0,li=v

15、lj-len,AOE网应用：关键路径,45,a2,a7,a6,a5,a4,a1,a3,a9,a8,ei,li,0,0,0,6,4,5,7,7,7,10,7,7,8,6,6,3,2,0,a10,a11,16,14,16,14,v2,v1,v3,v4,v5,v8,v6,v7,v9,a1=6,a4=1,a7=9,a10=2,a11=4,a8=7,a9=4,a5=1,a6=2,a3=5,a2=4,关键活动：li=ei的活动,AOE网应用：关键路径,46,显然 求ve的顺序应该是按拓扑有序的次序,而 求vl的顺序应该是按拓扑逆序的次序,因为 拓扑逆序序列即为拓扑有序序列的逆序列,因此 应该在拓扑排序的过

16、程中，另设一个“栈”记下拓扑有序序列,要找出关键路径，必须找出关键活动,即不按期完成就会影响整个工程完成的活动,关键路径上的所有活动都是关键活动 因此,只要找到了关键活动,就可以找到关键路径,AOE网应用：关键路径,47,AOV网，AOE网，都能表示工程各子工程的流程，一个用顶点表示活动，一个用边表示活动，但AOV网侧重表示活动的前后次序，AOE网除表示活动先后次序，还表示了活动的持续时间等，因此可利用AOE网解决工程所需最短时间及哪些子工程拖延会影响整个工程按时完成等问题。实际应用中采用那一种图，取决于要求解的问题。,一、有向无环图及其应用,2、关键路径,48,本 讲 小 结,重点：1、拓扑排序难点：1、关键路径,49,Homework:,给出下面AOE网中，各活动的最早开始时间和最迟开始时间，以及该AOE网的关键路径。,