数据结构拓扑排序例题 拓扑排序和关键路径是如何实现的?
浏览量:2257
时间:2021-03-11 14:51:06
作者:admin
拓扑排序和关键路径是如何实现的?
拓扑排序的实现步骤:AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下三个步骤,直到没有度为0的顶点为止;(1)选择度为0的顶点并输出;(2)删除网络中的顶点和所有外边缘;(3) 循环后,如果输出顶点的个数小于网络中的顶点个数,则输出“循环”,否则,输出顶点序列为拓扑序列。寻找关键路径的算法:(1)输入e弧<J,K>建立AOE网络的存储结构。(2) 从震源点V1开始,设ve(1)=0,求ve(J)2<=J<=n。(3)从交汇点VN开始,设VL(n)=ve(n),求VL(I)1<=I<=n-1。(4) 根据每个顶点的VE和VL值,计算每个弧s(activity)的最早开始时间e(s)和最晚开始时间l(s),其中e(s)=l(s)是关键activity。
拓扑排序和关键路径是如何实现的?
拓扑排序的实现步骤如下:
AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下三个步骤,直到没有度为0的顶点;
(1)选择度为0的顶点并输出;
(2)删除顶点从网络中选择度为0的顶点,在循环的末尾输出,如果输出的顶点数小于网络中的顶点数,则输出“循环”信息,否则输出的顶点序列是拓扑序列。
寻找关键路径的算法:
(1)输入e弧
(2)从源点V1开始,设ve(1)=0,求ve(J)2
(3)从汇点VN开始,设VL(n)=ve(n),求VL(I)1
(4)根据每个顶点的ve和VL值,找出每个弧s(活动)的最早开始时间e(s)和最晚开始时间l(s),其中e(s)=l(s)是关键活动。
版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
下一篇
成都新元素 成都祖马龙