fc2ブログ



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) を選択します。
uT に属し、vV - T に属する。
- エッジ (u, v) は、T に属するノードとV - T に属するノードをつなぐエッジの中で、重みが最小のものである。
vT に追加します。
この処理を、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 を選択します。
uT に追加すると同時に、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 を構成するエッジとなります。


primStep.gif

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) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ