最小全域木(Prim)

説明

最小全域木(全域木のうち、その辺群の重みの総和が最小になる木)を求めるアルゴリズム。既に到達した頂点集合からまだ到達していない頂点集合への辺のうち、コストが最小のものを選んでいくことによって、最小全域木を構成している。

計算量

• $O(E \log V)$

実装例

• prim($g$):= 連結な重み付きグラフ $g$ の最小全域木を求める。

template< typename T >
T prim(WeightedGraph< T > &g) {
  using Pi = pair< T, int >;
 
  T total = 0;
  vector< bool > used(g.size(), false);
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  que.emplace(0, 0);
  while(!que.empty()) {
    auto p = que.top();
    que.pop();
    if(used[p.second]) continue;
    used[p.second] = true;
    total += p.first;
    for(auto &e : g[p.second]) {
      que.emplace(e.cost, e.to);
    }
  }
  return total;
}

検証

AOJ GRL_2_A 最小全域木

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A"

#include "../../template/template.cpp"
#include "../template.cpp"

#include "../prim.cpp"

int main() {
  int V, E;
  scanf("%d %d", &V, &E);
  WeightedGraph< int > g(V);
  for(int i = 0; i < E; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }
  printf("%d\n", prim(g));
}