资源描述
,单击此处编辑母版标题样式,*,数 据 结 构,第 四十一课 拓扑排序和关键路径,数 据 结 构第 四十一课 拓扑排序和关键路径,1,第三十三课 拓扑排序和关键路径,本课主题：,拓扑排序和关键路径,教学目的：,拓扑排序和关键路径,教学重点：,关键路径,教学难点：,关键路径,授课内容：,第三十三课 拓扑排序和关键路径本课主题：拓扑排序和关键路,2,有向无环图的概念,有向无环图的定义,无环的有向图叫有向无环图，简称DAG图。,有向无环图的应用,有向无环图是描述工程或系统的进行过程的有效工具。一是工程能否顺利进行，二是估算工程完成所需的最短时间，这就是拓扑排序和关键路径问题。,有向无环图的概念有向无环图的定义,3,一拓扑排序,1、拓扑排序的基本概念,(1)AOV网,顶点表示活动，弧表示活动间的优先关系的有向图，叫,顶点表示活动的网（Activity On VertexNetwork）。,(2)拓扑序列,将AOV网上的所以顶点排成一个线性序列，且该序列满,足若在AOV网中，顶点vi到vj有一条路径，则在该线性序,列中vi必在vj的前面。这样的序列称为拓扑序列。,一拓扑排序1、拓扑排序的基本概念,4,(3)拓扑排序,对AOV网构造拓扑序列的操作叫拓扑排序。,(4)在AOV网中不应有环，否则就会自己以自己为先决条,件；若AOV网代表一个工程，则AOV网的一个拓扑序列,就是一个工程顺利完成的可行方案。,(3)拓扑排序,5,2、拓扑排序的方法,从图中选择一个入度为0的顶点输出；,从图中删除该顶点及源自该顶点的所有弧；,重复以上两步，直至全部顶点都输出，拓扑排序顺利完成。否则，若剩有入度非0的顶点，说明图中有环，拓扑排序不能进行。,2、拓扑排序的方法从图中选择一个入度为0的顶点输出；,6,3拓扑排序算法(1),在邻接表的顶点向量中，向量的每个元素再增加一个入,度域，存放各顶点的入度值。输出该顶点，删除源自该,顶点的弧就是将该顶点的邻接点的入度减1。实际实现,时，可设一个栈，存放入度为0的顶点，退栈就是输出顶,点，当邻接点的入度域减1减到0时，就将其入栈，拓扑,排序完成时，栈应为空。,3拓扑排序算法(1)在邻接表的顶点向量中，向量的每个元素再,7,3、拓扑排序算法(2),Status ToplogicalSort(ALGraph G),FindInDegree(G,indegree);,InitStack(S);,for(i=0;inextarc),k=padjvex;,if(!(-indegreek)Push(S,k);,if(countG.vexnum)return ERROR;,else return OK;,3、拓扑排序算法(3)while(!StackEmpty(,9,4、拓扑排序算法的分析,O（n+e）,4、拓扑排序算法的分析 O（n+e）,10,二关键路径,1,AOE网,用顶点表示事件，弧表示活动，弧上的权值表示活动持,续的时间的有向图叫AOE（Activity On Edge Network）,网。AOE网常用于估算工程完成时间。,二关键路径 1AOE网,11,2,AOE网研究的问题,完成整个工程至少需要多少时间；,哪些活动是影响工程的关键。,1956年，美国杜邦公司提出关键路径法，并于1957年首,先用于1000万美圆化工厂建设，工期比原计划缩短了4,个月。杜邦公司在采用关键路径法的一年中，节省了,100万美圆。,2AOE网研究的问题完成整个工程至少需要多少时间；,12,3关键路径的几个术语,关键路径 从源点到汇点的路径长度最长的路径叫关键路径。,活动开始的最早时间e(i),活动开始的最晚时间l(i)定义e(i)=l(i)的活动叫关键活动。,事件开始的最早时间ve(i),事件开始的最晚时间vl(i),3关键路径的几个术语关键路径 从源点到汇点的路径长度最长,13,设活动ai由弧(即从顶点j到k)表示，其持续时间记为dut(),则 e(i)=ve(j)l(i)=vl(k)-dut()(6_6_1),求ve(i)和vl(j)分两步：,从ve(1)=0开始向前递推,ve(j)=Max ve(i)+dut()(6_6_2),T,2,jn,其中T是所有以j为弧头的弧的集合。,从vl(n)=ve(n)开始向后递推,vl(i)=Min vl(j)-dut()(6_6_3),S,1,i n-1,其中S是所有以i为弧尾的弧的集合。,两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。,设活动ai由弧(即从顶点j到k)表示，其持续时间记,14,4求关键路径的算法(1),输入e条弧，建立AOE网的存储结构。,从源点v1出发，令ve(1)=0,求 ve(j)2=j=n。,从汇点vn出发，令vl(n)=ve(n),求 vl(i)1=inextarc),k=padjvex;,if(-indegreek=0)Push(S,k);,if(vej+*(p-info)vek)vek=vej+*(p-info);,4求关键路径的算法(2)Status Toplogical,16,4求关键路径的算法(3),if(countnextarc),k=padjvex;dut=*(p-info);,if(vlk-dutvlj)vlj=vlk-dut;,4求关键路径的算法(3)if(countG.vexnum,17,4求关键路径的算法(4),for(j=0;jnextarc),k=padjvex;dut=*(p-info);,ee=vej;el=vlk;,tag=(ee=el)?*:;,printf(j,kdut,ee,el,tag);,4求关键路径的算法(4)for(j=0;jG.vexnu,18,5求关键路径的实例模拟,5求关键路径的实例模拟,19,6求关键路径的算法分析,求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；,只有缩短关键活动的工期才,有可能,缩短工期；,若一个关键活动不在所有的关键路径上，减少它并不能减少工期；,只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。,6求关键路径的算法分析求关键路径必须在拓扑排序的前提下进行,20,六总结,回目录,上一课,下一课,六总结,21,
展开阅读全文