摘要
为了降低基于邻接矩阵的拓扑排序算法的复杂性,将单顶点算法框架扩展成集合算法框架,给出一些便于进行拓扑排序的有向无环图的性质。在此基础上,定义了适合进行弧删除操作和无前驱顶点判断的邻接矩阵运算,给出了有向弧邻接矩阵的存储方案,最终提出了一种时间和空间复杂度都比较低的拓扑排序算法。
In order to decrease the complexity of the topological sort algorithms which are based on adjacency matrix, the singlevertex algorithm framework was expanded to the set algorithm framework, and some properties of Directed Aeyelle Graph （DAG） propitious for topological sort were given. Based on these, some manipulations of the DAG＇s adjacency matrix were defined, a storage solution for DAG＇s adjacency matrix was given and a new topological sort algorithm with low computation and storage complexity was proposed.
出处
《计算机应用》
CSCD
北大核心
2007年第9期2307-2309,共3页
journal of Computer Applications
基金
武器装备预先研究项目(41306030102)
关键词
拓扑排序
邻接矩阵
集合算法框架
topological sort
adjacency matrix
set algorithm framework
