2008/11/30

ループ検出(2)

おお、昨日の話題をいけがみさんより丁寧な解説が。 確かに「木の循環」は変ですね。有向グラフにサイクルがあるかどうかの判定という ことですね。

O(m+n)の全走査アルゴリズムだけど、隣接グラフか行列を走査するにつれ マークしてく必要はやっぱりあるのですよね。

TAOCPの4巻で カバーされるんだろうか。このへんは。

(追記2008/11/30 19:13:09 PST):

Korte-Vegen の教科書によれば、topological sorting は TAOCP(Knuth, D.E. "The Art of Computer Programming; Vol.1; Fundamental Algorithms, Addison-Wesley, Reading 1968 (3rd ed. 1997) に言及されているとのことです。

ああ、topological sortingについては確かに1巻にありました。 Gaucheのutil.toposortモジュールはそのままTAOCPのやつを実装していたような。 うは、それでまさに循環が検出された時には "graph has circular dependency" ってエラーを出すようにしてる。 これそのまんまで良かったんだ。 入力形式が違っても同型になる問題に気づくってことは大事なのですなあ。

Tags: Programming, Gauche