プリム法/Prim-Algorithm ｃ＋＋
こんにちは、ハトムギです。
今回は、プリム法について書きます。
プリム法
グラフの情報が隣接行列で与えられている場合は、プリム法を用います。
今回は頂点数ｎの重み付き無向グラフの隣接行列を二次元配列M[i][j]に格納します。M[i][j]はiからjへの経路の重さです。
ちなみに無向グラフの場合M[i][j]=M[j][i]です。
int prim(int s)
プリム法で特別に必要なデータ構造は、最小全域木に属している点の集合を格納する配列のみです。（以下 int mst[]としておきます）
簡単なアルゴリズムは
任意の点をmstに追加します。（どこがスタート地点でも最小全域木の形、経路の重さの総和は変化しない）
次に、
すべての頂点がmstに属するまで以下を繰り返します。
頂点の集合をVとし最小全域木に属している頂点の集合をmstとしたとき、mst内の点とV-mst内の点をつなぐ辺の中から重さが最小のものをmstに追加します。
その間に、選択した辺を足し合わせておいたらすべての頂点がmstに入ったときには最小全域木の経路の重さの総和が求められています。
int prim(int s) {
int sum = 0;
for (int i = 0; i < n; i++) mst[i] = -1;
int numofmst = 0;
mst[numofmst++] = s;
for (int i = 0; i < n; i++) M[i][s] = -1;
while (numofmst != n) {
int min = 3000;
int m = n;
for (int i = 0; i < n; i++) {
if (mst[i] != -1) {
for (int ii = 0; ii < n; ii++) {
if (M[mst[i]][ii] == -1)continue;
if (min > M[mst[i]][ii]) {
min = M[mst[i]][ii];
m = ii;
}
}
}
}
sum += min;
mst[numofmst++] = m;
for (int i = 0; i < n; i++) M[i][m] = -1;
}
return sum;
}
- 最小全域木の経路の重さの総和を保存しておく、sumを初期化しておきます。
- グローバルに宣言していた、mst配列をを初期化します。
- mstに属している頂点の数を保存するnumofmstを保存します。
- main 関数内で受け取ったスタート地点のsをmstに格納して、sにもう一度到達できないので、s以外の点とsを結ぶ経路を-1にして消します。
- numofmstがｎになるまでループを繰り返します。
- ループの中は最小値の候補を走査するのが少しややこしいですが要するに、最小値を求めるアルゴリズムです。
- mstに属している点を探し、属していいる点から属していない点への経路がある場合、その時の経路が最小値の候補になります。
- 最小値が決まればその時の点をmstに最小値をsumにたし合わせます。ここで、最小値が決まった時の新しい点を保存しておく変数も必要だと気づきます。
- numofmstがnになればループを抜け出し、sumを返します。
