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

The Design and Implementation of Parallel Topological Sort Algorithm

文章对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.