トポロジカルソート
トポロジカルソートの別のアルゴリズムは深さ優先探索をベースにしている。このアルゴリズムではグラフの各ノードについて、トポロジカルソートを始めてからすでに訪れたノードに到達するまで深さ優先探索を行う。また、L への追加は先頭に行うことに注意。
上のアルゴリズムでノードnがリストLに追加されるのは、ノードnが依存している他のノード(グラフ中でnから到達可能な全てのノード)を訪れた後であることに注意。このアルゴリズムでは、ノードnが追加されるときnが依存するすべてのノードはすでにリストLに追加されていることが保証されている。そのようなノードはノードnからvisit()の再帰で到達するか、あるいはnを訪れるより前にすでに到達されているはずである。辺とノードは一度しか訪問されないのでこのアルゴリズムは線形時間しか必要としない。上の擬似コードはグラフに循環がある場合にそれをエラーとして検出することはできない。この深さ優先探索ベースのアルゴリズムは『アルゴリズムイントロダクション』で解説されている。Tarjan (1976) が最初に発表したものと思われる。
閉路を検出するには、下記の擬似コードで行える。
ISBN 476490408X。
↑ Tarjan, Robert E. (1976). “Edge-disjoint spanning trees and depth-first search”. Algorithmica 6 (2): 171–185. doi:10.1007/BF00268499.
↑ Vernet, Oswaldo; Markenzon, Lilian (1997). “Hamiltonian problems for reducible flowgraphs”. Proc. 17th International Conference of the Chilean Computer Science Society (SCCC '97). pp. 264–267. doi:10.1109/SCCC.1997.637099.