ferinの競プロ帳

競プロについてのメモ

トポロジカルソート

トポロジカルソートについて調べた内容のメモです。

トポロジカルソートとは

閉路がない有向グラフの各有向辺が順方向になるようにソートすることをトポロジカルソートと呼びます。DAG(有向無閉路グラフ)にのみ行うことができ、トポロジカルソートが行えればそのグラフはDAGであるといえます。
トポロジカルソート | グラフ | Aizu Online Judge

トポロジカルソートのアルゴリズム

入次数

入次数が0の頂点があれば、その頂点をソート後の結果に追加しその頂点と隣接した頂点の入次数をマイナス1する。これを入次数が0の頂点がなくなるまで繰り返すことでトポロジカルソートをすることができます。計算量はO(V+E)です。
有向非巡回グラフ(DAG)をトポロジカルソートする - マツシタケイタの技術ブログ(勉強中)


DFS

全ての点から深さ優先探索を行い、その帰りがけ順がトポロジカルソートの結果になります。計算量はO(V+E)です。

Topological sort