トポロジカルソート

トポロジカルソートは、依存関係のある複数の要素を依存関係の順序を崩さずに並べるソート.ノード数をNとしエッジ数をEとして、時間計算量はO(V+E)で完了する. プログラムに依存関係があるときや仕事の順序の決定などにトポロジカルソートは用いられる.

トポロジカルソートのアルゴリズムについて解説します. この問題は解決する方法は主に二つあります(片方はベースが探索です).どちらも線形時間の処理すなわちO(V+E)の時間計算量になります. ・Kahnの方法(トポロジカルソート) 解がなければ循環がある.特定のノードの依存先を求めにくい ・Tarjanの方法(深さ優先探索) こちらは循環があるかは別に確認が必要.特定のノードの依存先を求めやすい

Kahnの方法はいたってシンプルな方法です. 誰にも依存されていないノードはどんどん追加していいので、そのノードから追加します. すると、新しく誰にも依存されていないノードが出てくるので、先ほど追加したノードの後ろに追加していきます. あらかじめ用意する ・誰にも依存されいてないノードリスト それでは、以下に流れを説明します.

Tarjanの方法は、深さ優先探索です. グラフの上から深さ順に沿って、深く潜った帰り際に見つけたノードを登録していくことになります.必ずノードを追加していくときは、リストの先頭に加えます. リストへの登録するときにはそのノードに依存している全てのノードは登録されていることになります.(深さ優先探索の性質)

深さ優先探索に関してわからない場合は、リンクを確認ください.

解が複数あることに関しては先に述べた通りです.さきのkahnのソートの説明でもb,cやd,eはどちらを先に加えても構いませんでした. 複数解があるかどうか 解が複数あるかどうかはひとつ知る方法として、グラフの中にハミルトニアン路が含まれているかどうかがあります.もし含まれているなら1つしか解はありません.ないなら解は二つ以上あります. 全ての解を列挙したい トポロジカルソートの列挙(トポロジカルソートの数え上げ)は、動的計画法(DP)を用いて行うことができます.

トポロジカルソートの数え上げについてはリンク先の参照ください.

トポロジカルソートを用いることでDAG(有効非循環グラフ)の最短経路をO(V+E)のオーダで求めることができます.