トポロジカルソート
トポロジカルソート(topological sort)
閉路はたどりはじめの点とたどり終わりの点が同じ道
道はどの点も2回以上通らないようにたどったもの
tsortコマンドでトポロジカルソートが実装されている code:mermaid
flowchart LR
7 --> 11
5 --> 11
11 --> 2
3 --> 8
7 --> 8
8 --> 9
11 --> 9
3 --> 10
11 --> 10
code:mermaid
flowchart TD
7 --> 11
5 --> 11
11 --> 2
3 --> 8
7 --> 8
8 --> 9
11 --> 9
3 --> 10
11 --> 10
確認用
Q. トポロジカルソート
参考
L ← トポロジカルソートした結果を蓄積する空リスト
S ← 入力辺を持たないすべてのノードの集合
while S が空ではない do
S からノード n を削除する
L に n を追加する
for each n の出力辺 e とその先のノード m do
辺 e をグラフから削除する
if m がその他の入力辺を持っていなければ then
m を S に追加する
if グラフに辺が残っている then
閉路があり DAG でないので中断