2016 - 2024

感恩一路有你

数据结构拓扑排序例题 拓扑排序和关键路径是如何实现的?

浏览量: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)是关键活动。

数据结构拓扑排序例题 什么是拓扑排序 数据结构图的拓扑排序

版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。