计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2007年
9期
2307-2309
,共3页
马志奇%杨宏文%胡卫东%郁文贤
馬誌奇%楊宏文%鬍衛東%鬱文賢
마지기%양굉문%호위동%욱문현
拓扑排序%邻接矩阵%集合算法框架
拓撲排序%鄰接矩陣%集閤算法框架
탁복배서%린접구진%집합산법광가
为了降低基于邻接矩阵的拓扑排序算法的复杂性,将单顶点算法框架扩展成集合算法框架,给出一些便于进行拓扑排序的有向无环图的性质.在此基础上,定义了适合进行弧删除操作和无前驱顶点判断的邻接矩阵运算,给出了有向弧邻接矩阵的存储方案,最终提出了一种时间和空间复杂度都比较低的拓扑排序算法.
為瞭降低基于鄰接矩陣的拓撲排序算法的複雜性,將單頂點算法框架擴展成集閤算法框架,給齣一些便于進行拓撲排序的有嚮無環圖的性質.在此基礎上,定義瞭適閤進行弧刪除操作和無前驅頂點判斷的鄰接矩陣運算,給齣瞭有嚮弧鄰接矩陣的存儲方案,最終提齣瞭一種時間和空間複雜度都比較低的拓撲排序算法.
위료강저기우린접구진적탁복배서산법적복잡성,장단정점산법광가확전성집합산법광가,급출일사편우진행탁복배서적유향무배도적성질.재차기출상,정의료괄합진행호산제조작화무전구정점판단적린접구진운산,급출료유향호린접구진적존저방안,최종제출료일충시간화공간복잡도도비교저적탁복배서산법.
