[B! graph][*programming] Rion778のブックマーク

クラスカルのアルゴリズム - naoyaのはてなダイアリー

昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下

Rion778 2009/06/11

リンク

糞ネット弁慶

Rion778 2009/06/07

リンク

最小全域木問題(クラスカル法とプリム法) - ぬいぐるみライフ？

最小全域木問題を解くためのアルゴリズム「クラスカル法」と「プリム法」を使ってみた．最小全域木についてクラスカル法プリム法 PKUの問題クラスカル法による解答プリム法による解答メモリ使用量と実行時間の比較最小全域木についてまず，全域木(Spanning tree)とは連結グラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと．つまり，連結グラフから適当な辺を取り除いていき，閉路をもたない木の形にしたものが全域木となる．ここで，グラフの各辺に重みがある場合，重みの総和が最小になるように辺を選んで作った全域木のことを最小全域木(Minimum spanning tree)という．最小全域木を求めるアルゴリズムとしては以下の二つが有名である．クラスカル法 (Kruskal's algorithm) プリム法 (Prim's algorithm) いずれも貪欲