拓扑排序和关键路径精选课件.ppt

《拓扑排序和关键路径精选课件.ppt》由会员分享，可在线阅读，更多相关《拓扑排序和关键路径精选课件.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于拓扑排序和关键路径第一页，本课件共有32页AOV-网用顶点表示活动，用边来表示活动之间的先后关系的有向图称为顶点活动网，简称AOV-网。例如，计算机专业学生的学习就是一个工程，每一例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。程之间有领先关系，有的课程可以并行地学习。7.5.1拓扑排序第二页，本课件共有32页C1高等数学高等数学C2程序设计基础程序设计基础C3离散数学离散数学C

2、1,C2C4数据结构数据结构C3,C2C5高级语言程序设计高级语言程序设计C2C6编译方法编译方法C5,C4C7操作系统操作系统C4,C9C8普通物理普通物理C1C9计算机原理计算机原理C8课程代号课程代号课程名称课程名称先修课程先修课程第三页，本课件共有32页学生课程学习工程图学生课程学习工程图C8C3C5C4C9C6C7C1C2第四页，本课件共有32页n在在AOV网络中不能出现回路网络中不能出现回路,即环。如果出即环。如果出现了环，则意味着某项活动应以自己作为现了环，则意味着某项活动应以自己作为先决条件，这是荒谬的。先决条件，这是荒谬的。n因此，因此，对给定的对给定的AOV网络，必须先判断

3、它网络，必须先判断它是否存在有向环。是否存在有向环。第五页，本课件共有32页n检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造网络构造它的拓扑有序序列。即将各个顶点它的拓扑有序序列。即将各个顶点(代表各代表各个活动个活动)排列成一个线性有序的序列，使得排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系网络中所有应存在的前驱和后继关系都能得到满足。都能得到满足。n这种构造这种构造AOV网全部顶点的拓扑有序序列网全部顶点的拓扑有序序列的运算就叫做拓扑排序。的运算就叫做拓扑排序。n如果通过拓扑排序能将如果通过拓扑排序能将AOV网络的所有顶网络的所有顶点都排入一个拓扑有

4、序的序列中点都排入一个拓扑有序的序列中,则该网络则该网络中必定不会出现有向环。中必定不会出现有向环。第六页，本课件共有32页n如果如果AOV网络中存在环，此网络中存在环，此AOV网络所代网络所代表的工程是不可行的。表的工程是不可行的。n例如例如,对学生选课工程图进行拓扑排序对学生选课工程图进行拓扑排序,得得到的拓扑有序序列为到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2第七页，本课件共有32页拓扑排序的方法拓扑排序的方法输入输入AOV网络。令网络。令n为顶点个数。为顶点个数。在在

5、AOV网络中选一个没有直接前驱的顶点网络中选一个没有直接前驱的顶点,并输出之并输出之;从图中删去该顶点从图中删去该顶点,同时删去所有它发出同时删去所有它发出的有向边的有向边;重复以上重复以上、步步,直到直到全部顶点均已输出，拓扑有序序列形成，全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或拓扑排序完成；或图中还有未输出的顶点图中还有未输出的顶点,但已跳出处理循但已跳出处理循环。说明图中还剩下一些顶点环。说明图中还剩下一些顶点,它们都有直它们都有直接前驱。这时网络中必存在有向环。接前驱。这时网络中必存在有向环。第八页，本课件共有32页C0C1C4C3C2C5拓扑排序的过程拓扑排序的过程(a)

6、有向无环图有向无环图C4C5C1C0C3(b)输出顶点输出顶点C2C1C4C5C3(c)输出顶点输出顶点C0C2C0C4C5C1C3(d)输出顶点输出顶点C3第九页，本课件共有32页C1C4C5(e)输出顶点输出顶点C4C5C1(f)输出顶点输出顶点C1C5(g)输出顶点输出顶点C5最后得到的拓扑有序序列为最后得到的拓扑有序序列为C2,C0,C3,C4,C1,C5。它满足图中给出的所有前驱和后继关系，。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如对于本来没有这种关系的顶点，如C2和和C4，也排，也排出了先后次序关系。出了先后次序关系。(h)拓扑排序完成拓扑排序完成第十页，

7、本课件共有32页AOV网络及其邻接表表示网络及其邻接表表示C0C1C4C3C2C5C0C1C2C30C4C50012345indegreedatafirstarc1301031adjvexnextarc30501500150第十一页，本课件共有32页n在在邻邻接接表表中中增增设设一一个个数数组组indegree，记记录录各各顶顶点点入入度度。在在拓拓扑扑排排序序前前前前,初初始始化化入入度度数组。入度为零的顶点即无前驱顶点。数组。入度为零的顶点即无前驱顶点。n在算法中在算法中,使用栈存放入度为零的顶点使用栈存放入度为零的顶点,供选供选择和输出无前驱的顶点。择和输出无前驱的顶点。第十二页，本课件

8、共有32页n拓扑排序算法可描述如下：拓扑排序算法可描述如下：u入度为零的顶点入栈入度为零的顶点入栈;u当栈不空时当栈不空时,重复执行重复执行从顶点栈中退出一个顶点从顶点栈中退出一个顶点,并输出之并输出之;从从AOV网络中删去这个顶点和它发出网络中删去这个顶点和它发出的边的边,边的终顶点入度减一边的终顶点入度减一;如果边的终顶点入度减至如果边的终顶点入度减至0,则该顶点进则该顶点进栈栈;u如果输出顶点个数少于如果输出顶点个数少于AOV网络的顶点个网络的顶点个数数,则报告网络中存在有向环。则报告网络中存在有向环。第十三页，本课件共有32页拓扑排序的算法拓扑排序的算法voidTopologicalS

9、ort(ALGraphG)FindInDegree(G,indegree);/初始化初始化indegreeInitStack(S);for(i=0;iG.vexnum;i+)/入度为零的顶点入度为零的顶点if(indegreei=0)Push(S,i);/进栈进栈count=0;/对输出顶点计数对输出顶点计数第十四页，本课件共有32页while(!StackEmpty(S)Pop(S,i);/退栈退栈coutinextarc)k=p-adjvex;if(-indegreek=0)/顶点入度减顶点入度减1Push(S,k);/顶点的入度减至零顶点的入度减至零,进栈进栈第十五页，本课件共有32页7

10、.5.2关键路径关键路径一、一、AOE网网n如果在有向无环图中如果在有向无环图中,用有向边表示一个工程中的活用有向边表示一个工程中的活动动(Activity),用边上权值表示活动持续时间用边上权值表示活动持续时间(Duration),用顶点表示事件用顶点表示事件,则这样的有向图叫做则这样的有向图叫做用边表示活动的网络用边表示活动的网络,简称简称AOE(ActivityOnEdges)网。网。第十六页，本课件共有32页nAOE网络在某些工程估算方面非常有用。网络在某些工程估算方面非常有用。例如，可以使人们了解：例如，可以使人们了解：u完成整个工程至少需要多少时间完成整个工程至少需要多少时间(假设

11、网络假设网络中没有环中没有环)?u为缩短完成工程所需的时间为缩短完成工程所需的时间,应当加快哪应当加快哪些活动些活动?第十七页，本课件共有32页n从源点到汇点的路径可能不止一条，并且这从源点到汇点的路径可能不止一条，并且这些路径的长度也可能不同。些路径的长度也可能不同。完成不同路径完成不同路径的活动所需的时间虽然不同的活动所需的时间虽然不同,但只有各条路但只有各条路径上所有活动都完成了径上所有活动都完成了,整个工程才算完成。整个工程才算完成。n因此因此,完成整个工程所需的时间取决于从源完成整个工程所需的时间取决于从源点到汇点的最长路径长度点到汇点的最长路径长度,即在这条路径上即在这条路径上所有

12、活动的持续时间之和。所有活动的持续时间之和。这条路径长度最这条路径长度最长的路径就叫做长的路径就叫做关键路径关键路径(CriticalPath)。第十八页，本课件共有32页要找出关键路径，必须找出要找出关键路径，必须找出关键活动关键活动,即不按期即不按期完成就会影响整个工程完成的活动。完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动关键路径上的所有活动都是关键活动。因此。因此,只只要找到了关键活动要找到了关键活动,就可以找到关键路径。例如就可以找到关键路径。例如,下图就是一个下图就是一个AOE网。网。V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=

13、4a8=1第十九页，本课件共有32页二、相关术语二、相关术语事件事件Vi的最早发生时间的最早发生时间ve(i)是从是从源点源点V0到到顶点顶点Vi的最长路径长度。的最长路径长度。事件事件Vi的最迟的最迟发生发生时间时间vl(i)在在不不推推迟迟整整个个工工程程完完成成的的前前提提下下，事事件件Vi的的最最迟迟发生时间。发生时间。活动活动ai的最早开始时间的最早开始时间e(i)活动活动ai的最迟开始时间的最迟开始时间l(i)表示在不推迟整个工程完成的前提下，活动表示在不推迟整个工程完成的前提下，活动ai最迟必最迟必须开始进行的事件。须开始进行的事件。第二十页，本课件共有32页时间余量时间余量l(

14、i)e(i)表示活动表示活动ai的最早可能开始时间和最迟的最早可能开始时间和最迟允许开始时间的时间余量。允许开始时间的时间余量。l(i)=e(i)的活动称为关键活动的活动称为关键活动。第二十一页，本课件共有32页三、怎样求关键路径？三、怎样求关键路径？如何找如何找e(i)=l(i)的关键活动？的关键活动？n为找出关键活动为找出关键活动,需要求各个活动的需要求各个活动的e(i)与与l(i)，以，以判别是否判别是否l(i)=e(i)。设活动设活动ai由弧由弧表示，表示，且活动持续时间记为且活动持续时间记为dut(),则则e(i)=ve(j)l(i)=vl(k)-dut()VjVkai第二十二页，本

15、课件共有32页n如何求如何求ve(i)和和vl(i)？u求求ve(i)的递推公式的递推公式从从ve(0)=0开始，向前递推开始，向前递推 T,i=1,2,n-1T是所有以第是所有以第j个顶点为头的弧的集合。个顶点为头的弧的集合。例，求右图中例，求右图中顶点顶点V6的最早的最早发生时间。发生时间。V3V4V5V6a6=3a7=2a8=1266第二十三页，本课件共有32页V1V2V3V4V5V6顶点vevl032668V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1032668第二十四页，本课件共有32页u求求vl(i)的递推公式的递推公式从从vl(n-1)

16、=ve(n-1)开始，反向递推开始，反向递推 S,i=n-2,n-3,0S是所有以第是所有以第i个顶点为尾的弧的集合。个顶点为尾的弧的集合。例，求右图中例，求右图中顶点顶点V1的最迟的最迟发生时间。发生时间。V1V3V2a1=3a2=224第二十五页，本课件共有32页V1V2V3V4V5V6顶点vevl032668V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1042678042678第二十六页，本课件共有32页a1a2a3a4a5a6a7a8活动ell-e011000341220253660671341V1V3V2V4a1=3a2=2V5V6a6=3a

17、7=2a4=3a3=2a5=4a8=1V1V2V3V4V5V6顶点vevl032668042678第二十七页，本课件共有32页四、算法实现四、算法实现n实现步骤：实现步骤：输入输入e条弧条弧，建立，建立AOE-网的存储结构；网的存储结构；从源点从源点v0出发，令出发，令ve0=0，按拓扑有序求其余各顶点的最早，按拓扑有序求其余各顶点的最早发生时间发生时间vei（1in-1）。如果得到的拓扑有序序列中顶点个）。如果得到的拓扑有序序列中顶点个数小于网中顶点数数小于网中顶点数n，则说明网中存在环，不能求关键路径，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤算法终止；否则执行步骤。从汇点从

18、汇点vn出发，令出发，令vln-1=ven-1，按逆拓扑有序求其余各按逆拓扑有序求其余各顶点的最迟发生时间顶点的最迟发生时间vli（n-2i2）；）；根据各顶点的根据各顶点的ve和和vl的值，的值，求每条弧求每条弧s的最早发生时间的最早发生时间e(s)和和最迟发生时间最迟发生时间l(s)。若某条弧满足条件。若某条弧满足条件e(s)=l(s)，则为关键活动。，则为关键活动。第二十八页，本课件共有32页n n 算法实现算法实现算法实现算法实现StatusTopologicalOrder(ALGraphG,Stack&T)/求各顶点事件的最早发生时间求各顶点事件的最早发生时间ve（全局变量），（全局

19、变量），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号顶点的每个邻接点的入度减号顶点的每个邻接点的入度减1if(-indegreek=0)push(S,k)；if(vej

20、+*(pinfo)vek)vek=vej+*(pinfo)；if(countG.vexnum)returnERROR；/该有向网有回路该有向网有回路elsereturnOK；第二十九页，本课件共有32页StatusCriticalPath(ALGraphG)/G/G为有向网，输出为有向网，输出G G的各项关键活动的各项关键活动if(!TopologicalOrder(G,T)returnERROR;vl0.G.vexnum-1=ve0.G.vexnum-1;/初始化顶点事件的最迟发生时间初始化顶点事件的最迟发生时间while(!StackEmpty(T)/按逆拓扑有序求各顶点的按逆拓扑有序求各

21、顶点的vlvl值值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)/求求eeee，elel和关键活动和关键活动for(p=G.verticesj；p；p=pnextarc)k=padjvex；dut=*(pinfo)；ee=vej；el=vlk-dut；tag=(ee=el)?*:；printf(j,k,dut,ee,el,tag)；/输出关键活动输出关键活动第三十页，本课件共有32页n n算法时间复杂度分析算法时间复杂度分析在拓扑排序求在拓扑排序求在拓扑排序求在拓扑排序求vei i和逆拓扑有序求和逆拓扑有序求vl vli时，算法时，算法的时间复杂度为的时间复杂度为O(n+e e)，求各个活动的，求各个活动的ek k 和和lk时时复杂度为复杂度为O(e)，所以总的求关键路径的时间复杂度，所以总的求关键路径的时间复杂度为为O(n n+e e)。第三十一页，本课件共有32页感感谢谢大大家家观观看看第三十二页，本课件共有32页