拓扑排序与关键路径.ppt_第1页
拓扑排序与关键路径.ppt_第2页
拓扑排序与关键路径.ppt_第3页
拓扑排序与关键路径.ppt_第4页
拓扑排序与关键路径.ppt_第5页
已阅读5页,还剩8页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、拓扑排序与关键路径,拓扑排序,拓扑序列:设G是一个有n个顶点的有向图,G中的n个顶点构成一个线性序列L,且该序列L满足:若是有向图的一条边,则在线性序列中,顶点x必定在顶点y的前面,即该线性序列L形如 ,x,y, 或者 ,x,y,那么线性序列L就称为拓扑序列 将有向图的顶点排成一个拓扑序列的过程称为拓扑排序,拓扑排序,拓扑排序只能在不含回路的有向图上进行 对于不含回路的有向图来说,其顶点的拓扑序列可能不是唯一的 右图的拓扑序列是: v1,v2,v3,v4或 v1,v3,v2,v4,AOV网,无回路的有向图可以用来表示一个包含多项活动的工程计划。其中,顶点表示一项活动,有向边表示活动之间的优先关

2、系。例如,边表示“活动y只有在活动x完成之后才能开始”这一关系。 为了保证工程的顺利完成,各项活动都必须按照拓扑序列规定的顺序进行。 这种顶点表示某种活动,边表示活动之间优先关系的无回路有向图,称为顶点表示活动的网,简称AOV网,拓扑排序,如何对于一个给定的有向图进行拓扑排序? 1、任选一个入度为0的顶点x2、输出并删除x3、对于所有邻接于x的那些顶点,将它们的入度减1重复执行上述步骤,知道图中所有顶点都被输出为止 如果在上述执行过程中,发现找不到入度为0的顶点且已输出的顶点个数少于图中顶点数,则说明什么问题?,关键路径,在无回路的有向网络中,假设只有一个入度为0的顶点(称为源点)和一个出度为

3、0的顶点(称为汇点),则从源点到汇点之间的最长的路径称为关键路径 木桶原理,关键路径,上图中,源点v1到汇点v9的关键路径有几条?关键路径的长度为多少?,关键路径,无回路有向网络可以用来表示一个包含多项活动的工程计划:有向边表示某一项活动,边上的权表示完成这项活动需要的时间,中间的顶点表示“所有入边代表的活动已完成,出边代表的活动可以开始”这样一种状态或事件,其中源点表示工程的开始状态,汇点表示工程的结束状态 源点到汇点的某一条关键路径上边的权值之和表示完成工程的计划时间 通过求有向网络的关键路径,可以估算出整个工程从开始到结束至少需要多少时间,可以知道哪些是影响工程进度的关键活动(如果在关键

4、路径上有某一项活动没有按时完成,则整个工程就不能在计划时间内完成),AOE网,用边表示活动且只有一个源点与汇点的无回路有向网络称为边表示活动的网,建成AOE网 在AOE网中,边分为两类:关键活动和非关键活动,关键路径,如何来求一个AOE网中的关键路径? 在AOE网中,假定有n个顶点,源点为v1,汇点为vn,边的权值用wij表示 定义两个量:Ei:事件vi的可能的最早发生时间,它等于从源点v1到顶点vi的最长路径长度Li:在保证汇点事件在En时刻发生的前提下,事件vi允许的最迟发生时间,它等于En减去从顶点vi到汇点vn的最长路径长度,关键路径,如何求Ei和Li? 令E1=0,沿正向路径求Ej Ej=max(Ei+wij)|vi邻接到vj 令Ln=En,然后沿反向路径求Li Li=min(Lj-wij)|vj邻接到vi 求Ej按照拓扑排序顺序求,求Li按照逆拓扑排序求,关键路径,如何从某个事件最早开始时间Ei和最迟开始时间Li来看关键路径? 具体程序该如何实现?拓扑排序与逆拓扑排序,关键路径,练习(keyway.c/keyway.in/keyway.out) 输入一个AOE网的邻接矩阵形式,输出其所有的关键路径上的点,源点为1,汇点为n输入文件第一行为n,接下来是nn的矩阵形式,矩阵元素vij为0表示顶点i到j无边,非零表示有边,值就是边的权值输出文件为一行,即关键路

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论