トポロジカルソート
有向非巡回グラフ (DAG)
の各頂点に順序をつけて、どの頂点も出力先より手前に来るように並べる。
頂点を1列に並べて、矢印が一方向になる。
ソート方法
方法1
DFSで終端から構成する。
探索の帰りがけに頂点を並べて、全ての頂点を並べた後に反転させる。
練習問題
https://algo-method.com/tasks/963
方法2
BFSで始端から構成する。
入次数0の頂点を始端として、その頂点を元のグラフから削除する。
次に入次数0の頂点を並べて、その頂点を元のグラフから削除する。これを繰り返す。
練習問題
https://algo-method.com/tasks/964
#グラフ