拓扑排序和关键路径

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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;vG.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;iG.vexnum;i+)if(!indegreei)push(S,i);,count=0;/,对输出顶点计数,while(!EmptyStack(S),/while,if(countG.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;vG.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;iG.vexnum;i+