トポロジカルソート
Problem 79(2) - グラフ理論へ - ボクノス
の続きです。
自分が作ったアルゴリズムがトポロジカルソートだと言う名前に気づいてなかったので・・・。
ところでトポロジカルソートって何者!?
昨日、新宿でラーメン食った。
腹いっぱいになったので、渋谷のスタバでお茶して。
あ、そうそう、新宿行く前に池袋のジュンク堂でいい本見つけてさ・・・。
あれ?俺昨日何してたんだっけ・・・と思い出しながら並べてみる。
- 新宿→ラーメン
- ラーメン→渋谷→スタバ
- 池袋→ジュンク堂→ラーメン
話をまとめると、
池袋→ジュンク堂→新宿→ラーメン→渋谷→スタバ
となる。話が長かったらスゲー大変だ。
時系列がバラバラだった話を一本の線にして話をまとめる。これをトポロジカルソートというらしい。
Tarjanのアルゴリズム
前回作ったのも、トポロジカルソートの実装の一つらしいけど、無駄な部分があるので、
もうちょっと頭の良さそうな Tarjanのアルゴリズムを試してみます。
こちらもやることはスゲー単純。
適当な点から深さ優先検索します。
Aから始めて、一番深いとこFへ到達。そしたらFをプッシュ。巡ったFにはチェックを加えておきます。
深さ優先なので、Eをプッシュ、D,C,Bと巡るとあら不思議。トポロジカルソート出来ちゃった。
全ての点をチェックすればオケー。O(頂点数+辺の数)で完了です。
トポロジカル可能な正しいグラフなら、どの点からスタートしても必ず末尾に辿りつくはずだし、末尾からソートされる。dfsスゲー。
実装
ということでコーディング。
(define *graph* '((a b d) (b d c) (c d e f) (d e) (e f) (f))) (define (tsort g) (letrec ((acc '()) (iter (lambda (vec) (for-each (lambda (v) (if (not (member v acc)) (iter v))) (cdr (assq vec g))) (if (not (member vec acc)) (set! acc (cons vec acc)))))) (for-each (lambda (n) (iter (car n))) g) acc)) (tsort *graph*) ; (a b c d e f) (tsort (reverse *graph*)) ; (a b c d e f)
うぅんシンプル!!
(エラーチェックとかしてないけど)
非破壊で深さ優先
set!とfor-eachがイケてないので非破壊で。
(define (tsort g) (letrec ((iter (lambda (vec acc) (let ((res (fold (lambda (v a) (if (member v a) a (iter v a))) acc (cdr (assq vec g))))) (if (member vec res) res (cons vec res)))))) (fold (lambda (n acc) (iter (car n) acc)) '() g)))
クリーンだよ。
参考
- acm/icpcまとめサイト - グラフ/深さ優先探索
- 図がスゲーわかりやすい。今回はステップ1だけでオケー。
- Spaghetti Source - トポロジカルソート
- エラーチェック付き。激しく参考になりました。