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