Prim's Algorithm プリムのアルゴリズム
2006.04.26 22:52 グラフ 最小全域木
Prim's Algorithm は、グラフ G(V, E) の最小全域木 (MST) を求めるための、最も一般的なアルゴリズムです。基本的な考え方は以下のようになります。
グラフ G(V, E) のノード全体の集合を V、 MST に属するノードの集合を T とします。 |
|
1. | G(V, E) から任意のノード r を選び、それを MST のルートとして、T に追加します。 |
2. | 以下のようなエッジ (u, v) を選択します。 |
- u は T に属し、v は V - T に属する。 - エッジ (u, v) は、T に属するノードとV - T に属するノードをつなぐエッジの中で、重みが最小のものである。 |
|
v を T に追加します。 | |
この処理を、T = V になるまで繰り返します。 |
このアルゴリズムを実装するポイントは、各選択ステップで "どのように最小の重みをもつエッジを記録するか" です。Prim's Algorithm は以下のように実装します。
グラフ G(V, E) のノード全体の集合を V、 MST を属するノードの集合を T、 とし、各ノードに値 cost, pi を割り当てます。 |
|
1. |
初期状態で、T は空です。 |
G(V, E) から任意のノード r を選び、 cost[r] = 0 pi[r] = -1 と初期化します。 | |
2. | ノードの集合 V - T の中から、cost[u] が最も小さいノード u を選択します。 |
u を T に追加すると同時に、u に隣接しかつ V - T に属する全てのノード v に対する値を以下のように更新します。 |
|
もし、 エッジ (u, v) の重み ≦ cost[v] ならば、 cost[v] = エッジ (u, v) の重み pi[v] = u |
|
この処理を T = V となるまで繰り返します。 |
(cost[v]、pi[v]) には、T に属するノード u と、V - T に属するノード v をつなぐエッジの中で、重みが最小のエッジの情報が記録されます。cost[v] には重みを、pi[v] には、ノード u、つまり MST におけるノード v の親が記録されます。従って、各ステップで、ノード u を選択するという操作は、「T に属するノードと V - T に属するノードをつなぐエッジの中で、重みが最小のもの」を選ぶ操作に相当します。 また、u が選ばれた時点で、エッジ ( u, pi[u] ) が MST を構成するエッジとなります。

001 int N; 002 int M[MAX][MAX]; 003 004 void prim(){ 005 dist = 0.0; 006 007 bool visited[MAX]; 008 int cost[MAX]; 009 int pi[MAX]; 010 011 for ( int i = 0; i < N; i++ ){ 012 visited[i] = false; 013 cost[i] = INT_MAX; 014 } 015 016 cost[0] = 0; 017 pi[0] = -1; 018 019 while ( 1 ){ 020 int mincost = INT_MAX; 021 int u; 022 // cost が最小となるノード u を選択する 023 for ( int i = 0; i < N; i++ ){ 024 if ( !visited[i] && cost[i] < mincost ){ 025 mincost = cost[i]; 026 u = i; 027 } 028 } 029 030 // すべてのノードが MST に含まれたとき 031 if ( mincost == INT_MAX ) break; 032 033 visited[u] = true; 034 035 for ( int v = 0; v < N; v++ ){ 036 if ( visited[v] || M[u][v] == INT_MAX ) continue; 037 // 更新処理 038 if ( M[u][v] < cost[v] ){ 039 cost[v] = M[u][v]; 040 pi[v] = u; 041 } 042 } 043 } 044 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |