数据结构41-拓扑排序和关键路径课件.ppt

上传人(卖家):晟晟文业 文档编号:4107095 上传时间:2022-11-11 格式:PPT 页数:21 大小:86KB
下载 相关 举报
数据结构41-拓扑排序和关键路径课件.ppt_第1页
第1页 / 共21页
数据结构41-拓扑排序和关键路径课件.ppt_第2页
第2页 / 共21页
数据结构41-拓扑排序和关键路径课件.ppt_第3页
第3页 / 共21页
数据结构41-拓扑排序和关键路径课件.ppt_第4页
第4页 / 共21页
数据结构41-拓扑排序和关键路径课件.ppt_第5页
第5页 / 共21页
点击查看更多>>
资源描述

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只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。六总结六总结回目录 上一课 下一课

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(数据结构41-拓扑排序和关键路径课件.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|