一个带环检测的深度优先搜索拓扑排序算法  

A Topological Sort Algorithm Based on Depth-first Search with Cycles Detection

作　　者：付勇[1] 

机构地区：[1]新疆大学数学与系统科学学院,乌鲁木齐830046

出　　处：《电脑编程技巧与维护》2013年第4期63-68,共6页Computer Programming Skills & Maintenance

摘　　要：提出了一种带环检测功能的深度优先搜索拓扑排序算法,详细介绍了几种基本拓扑排序算法,分析了带环检测功能的深度优先搜索拓扑排序算法的意义和作用,并证明了该算法的完备性和正确性,给出了该算法的用C++编写的实现代码。This paper presents an algorithm based on depth-first search with circles detection. In the paper, several basic topological sort algorithms been description in detail, and analyzes the circles detection of the depth-first search topological sort algorithm meaning and function, and proves that the algorithm is completeness and correctness. Finally, it gives the algo- rithm realization code that is written in C＋＋.

关 键 词：有向图 拓扑排序 深度优先搜索 环检测 强连通分量 

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