2万+  知识点  标题检索     全文检索
       拓扑排序和关键路径
               AOV网
               在有向图中,若一顶点表示活动,用有向边表示活动之间的优先关系,则称这样的有向图为以顶点表示活动的网,简称AOV网。
               在AOV网中不应出现有向环。不存在回路的AOV网称为有向无环图或DAG图。检测的方法是对有向图构造其从顶点开始的拓扑有序序列,若图中所有顶点都在它的拓扑有序序列中,则该AOV网中必定不存在环。
               拓扑排序及其算法
               拓扑排序是将AOV网中所有顶点排成一个线性序列,该序列满足:若在AOV网中从顶点vivj有一条路径,则在该线性序列中,顶点vi必然在顶点vj之前。拓扑排序即指对AOV网构造拓扑序列的操作。
               对AOV网进行拓扑排序的方法如下。
               (1)在AOV网中选择一个入度为零的顶点且输出它。
               (2)从网中删除该顶点及与该顶点有关的所有边。
               (3)重复上述两步,直至网中不存在入度为零的顶点为止。
               若在AOV网中考察各顶点的出度,并按下列步骤进行排序,则称为逆拓扑排序。
               (1)在AOV网中选择一个没有后继的顶点且输出它。
               (2)从网中删除该顶点,并删去所有到达该顶点的弧。
               (3)重复上述两步,直至网中不存在出度为零的顶点为止。
               拓扑排序的时间复杂度为O(n+e)。
               AOE网
               若在带权有向图G中以顶点表示事件,以有向边表示活动,边上的权值表示该活动持续的时间,则这种带权有向图称为用边表示活动的网,简称AOE网。
               AOE网中不应存在有向回路。
               关键路径和关键活动
               从源点到汇点的路径中,长度最长的路径称为关键路径。关键路径上的所有活动均是关键活动。如果任何一项关键活动没有按期完成,则会影响整个工程的进度,而提高关键活动的速度可以缩短整个工程的工期。假设在n个顶点的AOE网中,顶点v0表示源点,顶点vn-1表示汇点,则计算关键活动及关键路径时可引入以下术语。
               .顶点事件的最早发生时间ve(j)。它是指从源点v0vj的最长路径长度(时间)。
               .顶点事件的最晚发生时间v1(i)。它是指在不推迟整个工程完成日期的前提下,事件vi所允许的最晚发生时间。
               .活动的最早开始时间e(k)。表示活动ak最早可开工时间。
               .活动的最晚开始时间l(k)。它是指在不推迟整个工程完成日期的前提下,允许该活动最晚开始的时间。
 
 相关知识点:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2019 All Rights Reserved 软考在线版权所有