2016-10-04から1日間の記事一覧

Kosaraju の強連結成分分解アルゴリズム

関数の呼び出しグラフの中から相互再帰をリストアップしたいとき等に強連結成分分解を利用します。 これまで、 30 年前に Tarjan のアルゴリズムで書いたものを使いまわしてきたのですが、 Kosaraju のアルゴリズムの方が実装が容易な場合があると考え直して…

日本語 Wikipedia の深さ優先探索

説明省略のリンク先に使おうかと読んでみたところ、 日本語 Wikipedia に記載されている while ループ版のアルゴリズムは、 訪問済みチェックを継続に入れる前におこなう方法で、 ゴミ集めなどで使われているやりかたです。 この方法は、 行きがけ順を気にせ…