トポロジカルソート

Scheme

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)))

クリーンだよ。

参考