Prim's Algorithm プリムのアルゴリズム

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 }