スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

強連結成分分解アルゴリズムの雰囲気

有向グラフの強連結成分を O(|V|+|E|) 時間で求めるのに、Kosaraju のアルゴリズムはよく知られている。
これは、もとのグラフと逆グラフに対してそれぞれ DFS を行うもので、強連結成分分解のアルゴリズムとしては最もポピュラーである。

Kosaraju のアルゴリズムがなぜ正しく動くのかが直観的にわからなかったので、気になって調べてみた。
この記事では雰囲気を説明するだけにとどめる。
完全な証明は、たとえば
[1] エイホ,ホップクロフト,ウルマン 『データ構造とアルゴリズム』
[2] コルメン,ライザーソン,リベスト,シュタイン 『アルゴリズムイントロダクション 第 2 巻』
にある。

Tags : グラフ理論, アルゴリズム

続きを読む

スポンサーサイト
プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。