AOV网中全拓扑排序算法的设计及应用

以顶点表示活动的网络(AOV网)可用来表示整个工程中各个子工程的先后次序制约关系,利用拓扑排序算法能求得子工程的线性序列———拓扑序列。按此序列安排各子工程,能保证整个工程的顺利完成。传统的拓扑排序算法基于栈结构实现,只能求得实际存在的多个拓扑序列中的一种,削弱了算法的实用价值。文中为了弥补这一缺陷,设计全拓扑排序算法求出了AOV网中实际存在的全部拓扑序列。给出了AOV网的定义及拓扑排序算法思想,分析了传统拓扑算法的不足,提出了一个全拓扑排序求解算法。并讨论了算法中用到的数据结构,以及算法的伪代码实现,通过一个应用实例验证了全拓扑排序算法的实用性和正确性。

Design and Application of Overall Topological Sort Algorithm in AOV Network

Activity on vertex network(AOV network)can present orders of all sub_-engineerings of one engineering,use topotogical sort algorithm to work out the linear sequence of all sub_-engineerings called topological sequence. If arrange sub_-engineerings according to the sequence,can ensure the whole engineering completed successfully.The traditional topological sort algorithm basedon stack can work out only one of all topological sequences, weakening its applied value. To remedy the defect,this paper designs an overall topological sort altorithm to work out all topological sequences existed in one AOV network. The paper presents the definition of AOV network and the thinking of topological sort algorithm, then it analyzes defect of the traditional topological sort algorithm, afterwards, it brings forward an overall topological sort algorithm. The paper discusses the data structures of the algorithm, and presents the implementation of the algorithm using pseudocode. At last an application of the certain algorithm is given , and its results show that the overall topological sort algorithm has high availability and exactitude.