20拓扑排序和关键路径

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,AOV,网,-,拓扑排序,有向无环图及其应用,AOE,网,-,关键路径,有向无环图,小结和作业,有向无环图,的应用,公用表达式,有向无环图,一、定义：,一个无环的有向图，称为有向无环图（,DAG,图）,V1,V2,V4,V5,V3,V7,V6,V8,V1,V2,V4,V5,V3,V7,V6,V8,DAG,图,有环的有向图,DAG = Directed Acyclic Graph,有向无环图,二、如何判断一个图是否是,DAG,？,V1,V2,V4,V5,V3,V7,V6,V8,DAG,图,V1,V2,V3,V8,V7,V6,V5,V4,V1,V2,V4,V5,V3,V7,V6,V8,非,DAG,图,V1,V2,V3,V8,V7,V6,V5,V4,有向无环图,二、如何判断一个图是否是,DAG,？,深度优先搜索没有出现指向祖先的回边，即：,没有一个顶点有一条边，指向遍历过程中先访问过的顶点（并且这些顶点的,DFS,函数没有执行完）,有向无环图,bool,DAG,(Graph,G),for,(v=0; v,G.vexnum,;,+,v),visitedv, =,FALSE,; /,访问标志数组初始化,InitStack(S,);/,存放顶点,for,(v=0; v=0; w=,NextAdjVex(G,v,w,),if (w in S) then,return(FALSE,);/,有回边,if(!visitedw,),if(!DFS,-DAG(G, w),return(FALSE,);,Pop(S,v);/v,的所有邻接点已经遍历完,return(TRUE,);, / DFS-T,公用表达式,用树表示表达式：,(,a+b,)*(b*(,c+d)+(c+d,)*e)*(,c+d,)*e),*,*,*,*,*,+,+,+,+,+,c,c,c,d,d,d,e,e,b,b,a,公用表达式,多次出现的变量和表达式通过共用，减少出现次数,*,*,*,*,*,+,+,+,+,+,c,c,c,d,d,d,e,e,b,b,a,*,*,*,*,+,+,+,c,d,e,b,a,拓扑排序,一、定义,由集合上的一个偏序关系得到集合的全序关系的操作,偏序：自反的、反对称的、传递的,全序：,R,是集合,X,上的偏序，对于集合,X,中的任何元素,x,y,，,如果都有,xRy,或者,yRx,则称,R,是全序关系,拓扑排序,B,D,A,C,B,D,A,C,偏序就是集合中的部分成员可以比较。,全序是集合中的任何成员之间都可以比较。,偏序,全序,拓扑排序,按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。,由此所得顶点的线性序列称之为拓扑有序序列,拓扑排序,用顶点表示活动，弧表示活动间的优先关系的有向图。,AOV,网（,Activity On Vertex,NetWork,）,AOV,网中不应该出现有向环：如果存在环，则某项活动以自己为先决条件，,拓扑排序,B,D,A,C,可求得拓扑有序序列,：,A B C D,或,A C B D,B,D,A,C,不能求得它的拓扑有序序列。,因为图中存在一个回路,B, C, D,拓扑排序,拓扑排序,-,方法,1,1,、从有向图中选取一个没有前驱的顶点，并输出之,;,2,、从有向图中删去此顶点以及所有以它为尾的弧,;,3,、重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。,拓扑排序,-,方法,1,a,c,g,b,d,h,f,e,b,h,a,c,d,g,f,e,拓扑序列,：,在算法中需要用定量的描述替代定性的概念,没有前驱的顶点 入度为零的顶点,删除顶点及以它为尾的弧 弧头顶点的入度减,1,拓扑排序,-,方法,1,Status,ToplogicalSort(ALGragh,G),FindInDegree(G,indegree,);,InitStack(S,);,for(i=0;i,G.vexnum;i+)if(!indegreei,) push(S,i);,count=0; /,对输出顶点计数,while (!,EmptyStack(S,) ,/while,if (count,G.vexnum,) return ERROR;,else return OK;,拓扑排序,-,算法,Status,ToplogicalSort(ALGragh,G),while (!,EmptyStack(S,) ,Pop(S, v);,+count;,printf(v,);,for (w=,FirstAdj(v,); w; w=,NextAdj(G,v,w,),-,indegree(w,);,/,弧头顶点的入度减,1,if (!,indegreew,) Push(S, w);,/for,/while,拓扑排序,-,算法,总的时间复杂度：,O(n+e,),算法分析：,拓扑排序,-,算法,拓扑排序,-,方法,2,a,c,g,b,d,h,f,e,b,h,a,c,d,g,f,e,拓扑序列,：,对有向无环图利用,深度优先搜索,进行拓扑排序。,拓扑排序,-,方法,2,a,c,g,b,d,h,f,e,b,h,a,c,d,g,f,e,此图的一个拓扑序列为：,a,c,g,b,d,h,f,e,退出,DFS,函数顺序：,e,f,g,d,c,a,h,b,拓扑排序,-,方法,2,最先退出,DFS,函数的顶点是出度为零的顶点，为拓扑排序序列中最后一个顶点。,因此，按,退出,DFS,函数的先后记录下来的顶点序列即为逆向的拓扑排序序列。,结论：,拓扑排序,-,方法,2,void,DFS-,ToplogicalSort,(Graph G,int,v,),/,如何确定,v,for,(v=0; v,G.vexnum,;,+,v),visitedv, =,FALSE,; /,访问标志数组初始化,InitStack(S,);/,存放顶点，按照出,DFS,的次序,for,(v=0; v=0; w=,NextAdjVex(G,v,w,),if,(,!,visitedw) DFS-T(G, w);,/,对,v,的尚未访问的邻接顶点,w,递归调用,DFS-T,Push(S, v);/,顶点,v,的,DFS,函数执行完毕,/ DFS-T,拓扑排序,-,练习,a,c,g,b,d,h,f,e,写出下图的所有的拓扑序列,关键路径,源点,汇点,事件,活动及其持续的时间,AOE-,网,(Activity on Edge):,边表示活动网。,a,1,=6,a,2,=4,v,8,v,1,V,2,V,3,v,4,v,5,v,6,v,8,v,7,v,9,a,3,=5,a,4,=1,a,5,=1,a,6,=2,a,7,=9,a,8,=7,a,9,=4,a,10,=2,a,11,=4,a,1,=6,a,4,=1,a,8,=7,a,11,=4,假设以,AOE,网表示一个施工流图，弧上的权值表示完成该项子工程所需的时间。,1,、完成整个工程至少需要多少时间？,2,、哪些活动是影响工程进度的关键？,关键路径,AOE-,网是一个带权的有向无环图，可用来估算工程的完成时间。,路径最长的路径叫做关键路径,影响工程进度的活动叫关键活动,关键路径上的活动一定是关键活动,关键路径,如何求关键路径,用,e(i),和,l(i),分别表示活动,a,i,的最早开始时间和最迟开始时间,e(i)-l(i),为活动,a,i,的时间余量,e(i)=l(i),的,活动是关键活动,如何求关键路径,ve(i,),：,表示事件,i,的最早开始时间,vl(i,),：,表示事件,i,的最迟开始时间,已知,ve(1)=0,，,计算其余顶点的,ve,值要按照,顶点拓扑排序后的次序,进行,ve(j,)=,max(ve(i,) +,dut,()T,T,是以,j,为头的弧的集合,a,1,=6,a,2,=4,v,8,v,1,V,2,V,3,v,5,v,8,v,7,v,9,a,4,=1,a,5,=1,a,7,=9,a,8,=7,a,10,=2,a,11,=4,V,i,到,V,j,的最长路径,如何求关键路径,vl(n-1)=ve(n-1),，然后,按照顶点,逆拓扑排序,后的次序求其余顶点的,vl,vl(i,)=,min(vl(j,) -,dut,()S,S,是以,i,为尾的弧的集合,a,1,=6,a,2,=4,v,8,v,1,V,2,V,3,v,5,v,8,v,7,v,9,a,4,=1,a,5,=1,a,7,=9,a,8,=7,a,10,=2,a,11,=4,如何求关键路径,用,e(i),和,l(i),分别表示活动,a,i,的最早开始间和最迟开始时间,显然有：,e(i,)=,ve(j,),l(i)=,vl(k)-dut(j,k,),j,k,a,i,如何求关键路径,a,1,=6,a,2,=4,v,8,v,1,V,2,V,3,v,4,v,5,v,6,v,8,v,7,v,9,a,3,=5,a,4,=1,a,5,=1,a,6,=2,a,7,=8,a,8,=7,a,9,=4,a,10,=2,a,11,=4,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,ve,vl,v,4,v,5,v,6,v,7,v,8,v,9,ve,vl,0,0,0,0,0,0,0,0,0,6,4,5,14,18,7,7,15,18,18,18,18,18,18,18,18,18,16,14,7,6,6,10,8,0,拓扑有序序列,:,v1 v2 v3 v4 v6 v5 v8 v7 v9,逆拓扑有序序列,:,v,9,v,7,v,8,v,5,v,2,v,3,v,6,v,4,v,1,如何求关键路径,a,1,a,2,a,3,e,l,a,4,a,5,a,6,a,7,a,8,a,9,a,10,a,11,6,4,5,1,1,2,8,7,4,2,4,0,0,0,6,4,5,7,7,7,15,14,0,2,3,6,6,8,8,7,10,16,14,a,1,=6,a,2,=4,v,8,v,1,V,2,V,3,v,4,v,5,v,6,v,8,v,7,v,9,a,3,=5,a,4,=1,a,5,=1,a,6,=2,a,7,=8,a,8,=7,a,9,=4,a,10,=2,a,11,=4,0, 0,6, 6,4, 6,5, 8,7, 7,7, 10,15, 16,14, 14,18, 18,如何求关键路径,a,1,=6,a,2,=4,v,8,v,1,V,2,V,3,v,4,v,5,v,6,v,8,v,7,v,9,a,3,=5,a,4,=1,a,5,=1,a,6,=2,a,7,=8,a,8,=7,a,9,=4,a,10,=2,a,11,=4,a,1,=6,a,4,=1,a,8,=7,a,11,=4,最终求得的关,键路径如下所示：,关键路径算法,1,）输入,n,个顶点和,e,条弧,，建立,AOE,网存储结构,2,）,求出网,G,的拓扑排序,令,ve0=0,求其余结点的最早发生时间,ve(j,)=,max(ve(i,) +,dut,() T,T,是以,j,为头的弧的集合,若得到拓扑排序中顶点个数,n,，说明,G,中存在环，算法终止。,关键路径算法,3,）求出,G,的逆向拓扑序列,从汇点出发，令,vl(n-1)=ve(n-1),求其余各顶点的最迟发生时间：,vl(i,)=,min(vl(j,) -,dut,(),S,S,是以,i,为尾的弧的集合,关键路径算法,4,）根据,2,）和,3,）中所得的,ve,和,vl,，求每条弧上的活动,a,i,的最早发生时间,e(i,),和,l(i,),e(i,)=,ve(j,),l(i,)=,vl(k)-dut(j,k,),j,k,a,i,5,）如果某条弧上的活动,a,i,满足,e(i,)=,l(i,),，则,a,i,为关键活动。,如何求关键路径,A,练习：求下图各活动弧,a,i,的,e(a,i,),和,l(a,i,),，个事件,v,j,的,ve(v,j,),和,vl(v,j,),，列出各关键路径。,B,C,D,E,F,G,H,W,X,1,6,3,4,2,7,5,10,6,11,17,12,9,13,8,21,16,关键路径算法,算法描述：,1,）有向网,AOE,采用邻接表作为存储结构,2,）栈,T,：拓扑序列顶点栈,3,）栈,S,：,0,入度顶点栈,4,）返回值：,ERROR,：图,G,中有回路,OK,：栈,T,返回图,G,的一个拓扑有序序列,关键路径算法,Status,ToplogicalOrder,(,ALGragh,G, Stack &T),FindInDegree(G,indegree,);,InitStack(S,);,for(i=0;i,G.vexnum;i+)if(!indegreei,) push(S,i);,Initstack(T,);,count=0; ve0.G.vexnum-1=0;,while (!,EmptyStack(S,) ,/while,if (count,nextarc,) k=p-,adjvex,;,if(-,indegree(k,)=),Push(S,k,); /,入度,-1,为,0,，则入栈,if(vej,+*(p-info),vek,),vek,=,vej,+*(p-info),/for,/while,if (count,nextarc,)k=p-,adjvex,;,dut,=*(p-info);,if(vlk-dut,vlj,),vlj,=,vlk-dut,; /end of for/end of while,/end of,CriticalPath,关键路径算法,Status,CriticalPath,(,ALGragh,G),/,输出,G,的关键活动,for(j,=0;j,nextarc,),k=p-,adjvex,;,dut,=*(p-info);,ee,=,vej;el,=,vlk-dut,; tag=(,ee,=el)?*:;,printf(j,k,dut,ee,el,tag,);,/end of,for(p,),/end of status,关键路径算法,Status,CriticalPath,(,ALGragh,G),/,输出,G,的关键活动,for(j,=0;j,nextarc,),k=p-,adjvex,;,dut,=*(p-info);,ee,=,vej;el,=,vlk-dut,; tag=(,ee,=el)?*:;,printf(j,k,dut,ee,el,tag,);,/end of,for(p,),/end of status,关键路径算法分析,1.,求关键路径的总的时间复杂度：,O(n+e,),2.AOE-,网求出的路径可能大于一条。,这种情况下只有同时提高所有关键路径上的活动的速度，才能使整个工期缩短。,小结和作业,1.,拓扑排序,2.,关键活动,本节主要内容：,1.,什么是拓扑排序,3.,拓扑排序算法,1.,什么是关键活动,3.,关键活动算法,2.,如何求关键活动,2.,如何进行拓扑排序,小结和作业,思考题：,下列关于,AOE,网的叙述中，不正确的是（ ）。,A,关键活动不按期完成就会影响整个工程的完成时间,B,任何一个关键活动提前完成，那么整个工程将会提 前完成,C,所有的关键活动提前完成，那么整个工程将会提前完成,D,某些关键活动提前完成，那么整个工程将会提前完成,作业：,7.9,，,7.10,