并行拓扑排序算法PTSA的设计与实现  

The Design and Implementation of Parallel Topological Sort Algorithm

作　　者：朱立华[1] 

机构地区：[1]南京邮电学院计算机科学与技术系,南京210003

出　　处：《计算机工程与应用》2004年第35期109-111,182,共4页Computer Engineering and Applications

摘　　要：文章对AOV网首次提出了一种基于层次的混合数据结构,按分层处理的方法实现并行拓扑排序算法PTSA,求得了AOV网中顶点的所有拓扑序列,克服了以往基于栈结构只能求得一种拓扑序列的缺陷。PTSA算法为工程中各子工程的串行或并行安排提供了确定的选择,提升了拓扑排序算法的实用价值。For the first time this paper brings forward a level-based mixed data structure,and achieves a Parallel Topological Sort Algorithm(PTSA)in the level-based method.Meanwhile it gets all the feasible topological lists of all vertexes in an Activity On Vertex(AOV)network.It mends the limitation of the certain Topological Sort Algorithm based on stack which can work out only one topological list.PTSA provides many possible choices for all sub-projects in a project which will be arranged in serial or parallel way,so PTSA improves the applied value of Topological Sort Algorithm.

关 键 词：AOV网 拓扑排序 并行拓扑排序算法PTSA 混合数据结构 十字队列 拓扑序列 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]