一种新的基于邻接矩阵的拓扑排序算法  

New topological sort algorithm based on adjacency matrix

作　　者：马志奇[1] 杨宏文[1] 胡卫东[1] 郁文贤[1] 

机构地区：[1]国防科学技术大学ATR实验室,长沙410073

出　　处：《计算机应用》2007年第9期2307-2309,共3页journal of Computer Applications

基　　金：武器装备预先研究项目(41306030102)

摘　　要：为了降低基于邻接矩阵的拓扑排序算法的复杂性,将单顶点算法框架扩展成集合算法框架,给出一些便于进行拓扑排序的有向无环图的性质。在此基础上,定义了适合进行弧删除操作和无前驱顶点判断的邻接矩阵运算,给出了有向弧邻接矩阵的存储方案,最终提出了一种时间和空间复杂度都比较低的拓扑排序算法。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.

关 键 词：拓扑排序 邻接矩阵 集合算法框架 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]