トップ > グラフ > トポロジカルソート

トポロジカルソート

グラフ グラフ-トポロジカルソート AtCoder Python

DAG（閉路のない有向グラフ）の辺が左から右に向くように，頂点を左から右に一列に並べる方法．

「有向グラフをトポロジカルソートできなければ閉路がある」という使い方もできる．

考え方

  1. 各頂点に入ってくる辺の本数（入次数，indegree）を配列indegに記録する．
  2. 入次数ゼロの頂点を入れるリスト・キュー・スタックを用意する（どういう順序で取り出したいかに応じて選択する）．以下ではキューqを使う．
  3. トポロジカルソートの結果を保存するリストansを用意する．
  4. qが空になるまで次の操作を行う
    1. qから頂点$v$を1つ取り出す（qから削除する）．
    2. $v$をansに追加する．
    3. $v$を始点とする辺を全て見て，その辺の終点の頂点の入次数を-1し，もしゼロになればqに追加する．
  5. すべての頂点がansに入れば，トポロジカルソート完了．入っていないものがあれば，閉路がある（トポロジカルソートできない）．

例

  • 閉路検出：トポロジカルソートで検出できる．
  • 「数字を頂点」，「順序関係を辺」と考えてDAGの問題にすれば，トポロジカルソートが使えるかも．
  • 「うまい具合に取り出せ」，「うまい具合に並べろ」という問題は，グラフ化してトポロジカルソートが使えるかも（「閉路があれば解無し」といえないか？）．


参考