深さ優先探索によるトポロジカルソート
トポロジカルソートのアルゴリズムは、『プログラマのうちあけ話―続・プログラム設計の着想』を読んで学びました。この本では次の方法により、トポロジカルソートします。
入力辺がないノードをキュー q に入れる while (q に要素が含まれる): node = q.pop() print(node) nodeの出力辺を全て削除する 入力辺がないノードをキュー q に入れる(ただし、printしたnodeは除く)
トポロジカルソート - Wikipedia をみますと、上記アルゴリズムの他に、深さ優先探索による方法でトポロジカルソートを行うアルゴリズムが書かれてあります。
深さ優先探索によるトポロジカルソートのプログラムを Lua で書いてみました。
入力ファイルとして、Problem 79 - Project Eulerのkeylog.txtを使います。
tsort コマンド
tsort (Unix) - Wikipedia, the free encyclopedia というトポロジカルソートを行うコマンドがあるようです。この tsort コマンドをつかって、トポロジカルソートしてみました。
% awk '{ split($1, a, ""); print a[1], a[2], a[2], a[3] }' < keylog.txt | tsort
7
3
1
6
2
8
9
0
