最小全域木の基本と、それに関連する知識を簡単にまとめておきます。最後に最小全域木に関する問題を解きます。

最小全域木

全域木

グラフGがあるとします。そして、その部分グラフG'を考えます。G' が G の全ての頂点を含み、かつ辺をできるだけ多く含む木である場合、G' を G の全域木（spanning tree）と言います。木は閉路を持たないグラフです。

f:id:programgenjin:20190318113316p:plain — G

f:id:programgenjin:20190318113347p:plain — Gの全域木１

f:id:programgenjin:20190318113411p:plain — Gの全域木２

上の図のように、全域木は一つであるとは限りません。

最小全域木

グラフGが重み付きグラフである場合を考えます。重み付きグラフは、グラフの各辺に値（重みという）が与えられているようなグラフのことです。上で見たように、Gの全域木は複数ありえますが、それらのうち各辺の重みの和が最小になるような全域木のことを最小全域木（Minimum Spanning Tree, MST）と言います。

プリムのアルゴリズム

最小全域木を求めるアルゴリズムの１つが次のPrimのアルゴリズムです。

グラフに属する全ての頂点の集合をV、最小全域木に属する頂点の集合をTとする。

１つの頂点を始点として任意に選び、Tに追加する。
V = Tとなるまで以下を繰り返す：
- V - T（最小全域木に含まれない頂点の集合）とTを結ぶ辺の中で、最小の重みを持つ辺を選び、その辺で結ばれている頂点をTに追加する。

Tに追加されるのが常にV - Tの頂点であることから、同じ頂点が重複してTに追加されることがなく、したがって閉路が形成されません。これにより最小全域木を構成することができます。

Primのアルゴリズムのイメージを構築するのにはこちらの記事が役立つと思います。

問題を解いてみる

次の問題を解きます。

最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge

・存在しない辺の重みは-1で与えられますが、隣接行列でその値をINFTYにしておきます。INFTYはどの辺の重みよりも大きな値とします。

・各頂点の状態を記録するために、次のように色を用います。

black：Tに属する
gray ：Tに属する頂点に隣接する
white：それ以外

・Tから頂点vに到達するのに必要なコスト（辺の重み）をcost[v]とします。最初に全てのvに対してcost[v]をINFTYに初期化します。ある頂点uがTに加わった時、uに隣接する頂点のcostを更新していけばOKです。

解答例：

#include<iostream>
using namespace std;

#define INFTY 2001
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define N 100

// 最小全域木を構成し、重みの総和を返す関数
int prim(int n, int A[N][N]) {
  int i, vertex, min_cost, sum_weight, cost[N], color[N];
  // 初期化
  for (i = 0; i < n; i++) {
    cost[i] = INFTY;
    color[i] = WHITE;
  }
  cost[0] = 0;
  color[0] = GRAY;
  sum_weight = 0;
  
  while (1) {
    // Tに隣接する頂点の中で最小のコストを持つものを選ぶ
    vertex = -1;
    min_cost = INFTY;
    for (i = 0; i < n; i++) {
      if (color[i] == GRAY && cost[i] < min_cost) {
        min_cost = cost[i];
        vertex = i;
      }      
    }
    // T = V ならば終了
    if (vertex == -1) break;

    color[vertex] = BLACK;  // vertexをTに加える
    sum_weight += cost[vertex];

    // vertexに隣接し、Tに属していない頂点のコストを更新
    for (i = 0; i < n; i++) {
      if (color[i] != BLACK && A[vertex][i] < INFTY) {
        color[i] = GRAY;
        if (cost[i] > A[vertex][i]) cost[i] = A[vertex][i];
      }
    }
  }

  return sum_weight;
}


// 最小全域木の辺の重みの和を計算する関数
int sum_weight(int n, int parent[], int A[N][N]) {
  int sum = 0;
  
  for (int i = 1; i < n; i++) sum += A[i][parent[i]];
  
  return sum;
}

int main() {
  int i, j, n, w, A[N][N];

  cin >> n;
  // 隣接行列が与えられる
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      cin >> w;
      if (w == -1) A[i][j] = INFTY;
      else A[i][j] = w;
    }
  }

  cout << prim(n, A) << endl;

  return 0;
}