20拓扑排序和关键路径

AOV网-拓扑排序有向无环图及其应用AOE网-关键路径有向无环图小结和作业有向无环图的应用公用表达式有向无环图一、定义：一个无环的有向图，称为有向无环图（DAG图）V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8DAG图有环的有向图DAG=DirectedAcyclicGraph有向无环图二、如何判断一个图是否是DAG？V1V2V4V5V3V7V6V8DAG图V1V2V3V8V7V6V5V4V1V2V4V5V3V7V6V8非DAG图V1V2V3V8V7V6V5V4有向无环图二、如何判断一个图是否是DAG？深度优先搜索没有出现指向祖先的回边，即：没有一个顶点有一条边，指向遍历过程中先访问过的顶点（并且这些顶点的DFS函数没有执行完）有向无环图boolDAG(GraphG){for(v=0;vG.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化InitStack(S);//存放顶点for(v=0;vG.vexnum;++v){if(!visited[v])if(!DFS-DAG(G,v))return(FALSE);//对尚未访问的顶点调用DFS-DAG}returnTRUE;}有向无环图BoolDFS-DAG(GraphG,intv){//从顶点v出发，深度优先搜索遍历连通图Gvisited[v]=TRUE;Push(S,v);for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)){{if(winS)thenreturn(FALSE);//有回边if(!visited[w]){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)*****+++++cccdddeebba公用表达式多次出现的变量和表达式通过共用，减少出现次数*****+++++cccdddeebba****+++cdeba拓扑排序一、定义由集合上的一个偏序关系得到集合的全序关系的操作偏序：自反的、反对称的、传递的全序：R是集合X上的偏序，对于集合X中的任何元素x,y，如果都有xRy或者yRx,则称R是全序关系拓扑排序BDACBDAC•偏序就是集合中的部分成员可以比较。•全序是集合中的任何成员之间都可以比较。偏序全序拓扑排序按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列拓扑排序用顶点表示活动，弧表示活动间的优先关系的有向图。AOV网（ActivityOnVertexNetWork）AOV网中不应该出现有向环：如果存在环，则某项活动以自己为先决条件，拓扑排序BDAC可求得拓扑有序序列：ABCD或ACBDBDAC不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}拓扑排序拓扑排序---方法11、从有向图中选取一个没有前驱的顶点，并输出之;2、从有向图中删去此顶点以及所有以它为尾的弧;3、重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。拓扑排序---方法1acgbdhfebhacdgfe拓扑序列：在算法中需要用定量的描述替代定性的概念没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减1拓扑排序---方法1StatusToplogicalSort(ALGraghG){FindInDegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;i++){if(!indegree[i])push(S,i);}count=0;//对输出顶点计数while(!EmptyStack(S)){…………}//whileif(countG.vexnum)returnERROR;elsereturnOK;}拓扑排序---算法StatusToplogicalSort(ALGraghG){………………while(!EmptyStack(S)){Pop(S,v);++count;printf(v);for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){--indegree(w);//弧头顶点的入度减1if(!indegree[w])Push(S,w);}//for}//while………………}拓扑排序---算法总的时间复杂度：O(n+e)算法分析：拓扑排序---算法拓扑排序---方法2acgbdhfebhacdgfe拓扑序列：对有向无环图利用深度优先搜索进行拓扑排序。拓扑排序---方法2acgbdhfebhacdgfe此图的一个拓扑序列为：acgbdhfe退出DFS函数顺序：efgdcahb拓扑排序---方法2最先退出DFS函数的顶点是出度为零的顶点，为拓扑排序序列中最后一个顶点。因此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑排序序列。结论：拓扑排序---方法2voidDFS-ToplogicalSort(GraphG,intv){//如何确定vfor(v=0;vG.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化InitStack(S);//存放顶点，按照出DFS的次序for(v=0;vG.vexnum;++v){if(!visited[v])DFS-T(G,v);//对尚未访问的顶点调用DFS}while(!Empty(S)){//输出拓扑排序的结果Pop(S,v);printf(“%d”,v)}}拓扑排序---方法2voidDFS-T(GraphG,intv){//从顶点v出发，深度优先搜索遍历连通图Gvisited[v]=TRUE;for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)){if(!visited[w])DFS-T(G,w);}//对v的尚未访问的邻接顶点w递归调用DFS-TPush(S,v);//顶点v的DFS函数执行完毕}//DFS-T拓扑排序---练习acgbdhfe写出下图的所有的拓扑序列关键路径源点汇点事件活动及其持续的时间AOE-网(ActivityonEdge):边表示活动网。v8v1V2V3v4v5v6v8v7v9a6=2假设以AOE网表示一个施工流图，弧上的权值表示完成该项子工程所需的时间。1、完成整个工程至少需要多少时间？2、哪些活动是影响工程进度的关键？关键路径AOE-网是一个带权的有向无环图，可用来估算工程的完成时间。•路径最长的路径叫做关键路径•影响工程进度的活动叫关键活动•关键路径上的活动一定是关键活动关键路径如何求关键路径•用e(i)和l(i)分别表示活动ai的最早开始时间和最迟开始时间•e(i)-l(i)为活动ai的时间余量•e(i)=l(i)的活动是关键活动如何求关键路径ve(i)：表示事件i的最早开始时间vl(i)：表示事件i的最迟开始时间已知ve(1)=0，计算其余顶点的ve值要按照顶点拓扑排序后的次序进行ve(j)=max(ve(i)+dut(i,j))i,j∈T,T是以j为头的弧的集合v8v1V2V3v5v8v7v9Vi到Vj的最长路径如何求关键路径vl(n-1)=ve(n-1)，然后按照顶点逆拓扑排序后的次序求其余顶点的vlvl(i)=min(vl(j)-dut(i,j))i,j∈S,S是以i为尾的弧的集合v8v1V2V3v5v8v7v9如何求关键路径用e(i)和l(i)分别表示活动ai的最早开始间和最迟开始时间显然有：e(i)=ve(j)l(i)=vl(k)-dut(j,k)jkai如何求关键路径v8v1V2V3v4v5v6v8v7v9a6=2v1v2v3v4v5v6v7v8v9vevlv4v5v6v7v8v9vevl0000000006451418771518181818181818181816147661080拓扑有序序列:v1v2v3v4v6v5v8v7v9逆拓扑有序序列:v9v7v8v5v2v3v6v4v1如何求关键路径a1a2a3ela4a5a6a7a8a9a10a1164511287424000645777151402366887101614v8v1V2V3v4v5v6v8v7v9a6=20,06,64,65,87,77,1015,1614,1418,18如何求关键路径v8v1V2V3v4v5v6v8v7v9a6=2最终求得的关键路径如下所示：关键路径算法1）输入n个顶点和e条弧j,k，建立AOE网存储结构2）求出网G的拓扑排序令ve[0]=0,求其余结点的最早发生时间ve(j)=max(ve(i)+dut(i,j))i,j∈T,T是以j为头的弧的集合若得到拓扑排序中顶点个数n，说明G中存在环，算法终止。关键路径算法3）求出G的逆向拓扑序列从汇点出发，令vl(n-1)=ve(n-1)求其余各顶点的最迟发生时间：vl(i)=min(vl(j)-dut(i,j))i,j∈S,S是以i为尾的弧的集合关键路径算法4）根据2）和3）中所得的ve和vl，求每条弧上的活动ai的最早发生时间e(i)和l(i)e(i)=ve(j)l(i)=vl(k)-dut(j,k)jkai5）如果某条弧上的活动ai满足e(i)=l(i)，则ai为关键活动。如何求关键路径A练习：求下图各活动弧ai的e(ai)和l(ai)，个事件vj的ve(vj)和vl(vj)，列出各关键路径。BCDEFGHWX163427510611171291382116关键路径算法算法描述：1）有向网AOE采用邻接表作为存储结构2）栈T：拓扑序列顶点栈3）栈S：0入度顶点栈4）返回值：ERROR：图G中有回路OK：栈T返回图G的一个拓扑有序序列关键路径算法StatusToplogicalOrder(ALGraghG,Stack&T){FindInDegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;i++){if(!indegree[i])push(S,i);}Initstack(T);count=0;ve[0..G.vexnum-1]=0;while(!EmptyStack(S)){…………}//whileif(countG.vexnum)returnERROR;elsereturnOK;}关键路径算法StatusToplogicalOrder(ALGraghG,Stack&T){…………while(!EmptyStack(S)){Pop(S,v);Push(T,j);++count;//j号顶点入栈Tfor(p=G.vertices[j].firstarc;p;p=p-nextarc){k=p-adjvex;if(--indegree(k)==)Push(S,k);//入度-1为0，则入栈if((ve[j]+*(p-info))ve[k])ve[k]=ve[j]+*(p-info)}//for}//whileif(countG.vexnum)returnERROR;elsereturnOK;}关键路径算法StatusCriticalPath(ALGraghG){//输出G的关键活动if(!)ToplogicalOrder(G,T)returnERROR;vl[0..G.vexnum-1]=ve[0..G.vexnum-1];//用ve初始化vlwhile(!stackEmpty(T)){pop(T,j);for(p=G.vertices[j].firstarc;p;p=p-nextarc){k=p-adjvex;dut=*(p-info);if(vl[k]-dutvl[j])vl[j]=vl[k]-dut;}//endoffor}//endofwhile…………}//endo