深さ優先探索版
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/24 15:50 UTC 版)
「トポロジカルソート」の記事における「深さ優先探索版」の解説
トポロジカルソートの別のアルゴリズムは深さ優先探索をベースにしている。このアルゴリズムではグラフの各ノードについて、トポロジカルソートを始めてからすでに訪れたノードに到達するまで深さ優先探索を行う。また、L への追加は先頭に行うことに注意。 L ← トポロジカルソートされた結果の入る空の連結リストfor each ノード n do visit(n)function visit(Node n) if n をまだ訪れていなければ then n を訪問済みとして印を付ける for each n の出力辺 e とその先のノード m do visit(m) n を L の先頭に追加 上のアルゴリズムでノードnがリストLに追加されるのは、ノードnが依存している他のノード（グラフ中でnから到達可能な全てのノード）を訪れた後であることに注意。このアルゴリズムでは、ノードnが追加されるときnが依存するすべてのノードはすでにリストLに追加されていることが保証されている。そのようなノードはノードnからvisit()の再帰で到達するか、あるいはnを訪れるより前にすでに到達されているはずである。辺とノードは一度しか訪問されないのでこのアルゴリズムは線形時間しか必要としない。上の擬似コードはグラフに循環がある場合にそれをエラーとして検出することはできない。この深さ優先探索ベースのアルゴリズムは『アルゴリズムイントロダクション』で解説されている。Tarjan (1976) が最初に発表したものと思われる。 閉路を検出するには、下記の擬似コードで行える。 L ← トポロジカルソートされた結果の入る空の連結リストfor each ノード n do if n に印が付いていない then visit(n)function visit(Node n) if n に「一時的」の印が付いている then 閉路があり DAG でないので中断 else if n に印が付いていない then n に「一時的」の印を付ける for each n の出力辺 e とその先のノード m do visit(m) n に「恒久的」の印を付ける n を L の先頭に追加
※この「深さ優先探索版」の解説は、「トポロジカルソート」の解説の一部です。
「深さ優先探索版」を含む「トポロジカルソート」の記事については、「トポロジカルソート」の概要を参照ください。
- 深さ優先探索版のページへのリンク
