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

摘要：

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

关键词：以顶点表示活动的网络、拓扑排序、全拓扑排序算法、拓扑序列

所属期刊栏目：14

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金70271050

在线出版日期：2004-12-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：123-125