Kruskal's Algorithm クラスカルのアルゴリズム
2006.04.26 22:53 グラフ 最小全域木
Kruskal's Algorithm は、グラフ G(V, E) の MST を求めるためのアルゴリズムです。これも Greedy Algorithm で、各計算ステップで、最も適したエッジを選び、MST を求めます。このアルゴリズムを実装するために必要なデータ構造が Disjoint Sets です。Kruskal's Algorithm は以下のように実装します。
グラフ G(V, E) のノード全体の集合を V、 エッジ全体の集合を E、 MST に属するノードの集合を T とし、 Disjoint Sets のデータ構造 dset を用意します。 |
|
1. | V の全ての要素 v を互いに素な集合とします つまり、全ての v に対して dset.makeSet( v ) を行います。 |
2. | E を、重みが小さい順に整列します。 |
3. | E から順番にエッジ (u, v) を取得し、以下の処理を行います。 |
もし u と v が同じ集合に属していないならば つまり、dset.findSet( u ) ≠ dset.findSet( v ) ならば、 u, v を T に追加し、 u, v を合併する。すなわち dset.union( u, v ) を行います。 |
class edge{ public: int source, target; double cost; edge(){} edge( int source, int target, double cost ): source(source), target(target), cost(cost){} bool operator < ( const edge &e ) const{ return cost < e.cost; } }; int N; vector<edge> edges; void kruskal( vector<edge> &mst ){ sort( edges.begin(), edges.end() ); DisjointSet dset = DisjointSet( N ); for ( int i = 0; i < N; i++ ) dset.makeSet( i ); int source, target; for ( int i = 0; i < edges.size(); i++ ){ edge e = edges[i]; if ( dset.findSet( e.source ) != dset.findSet( e.target ) ){ mst.push_back( e ); dset.union( e.source, e.target ); } } }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |