説明

最小全域木(全域木のうち、その辺群の重みの総和が最小になる木)を求めるアルゴリズム。

それぞれの連結成分について、他の連結成分を結ぶ重みが最小の辺を求めて縮約を繰り返すことにより最小全域木を求める。繰り返し回数は $O(\log V)$ 回なので、普通の最小全域木であれば $O(E \log V)$ で求めることができる。

特殊な重みの場合でも解けることが多いのが強みである。

計算量

  • $O(E \log V)$

実装例

依存ライブラリ Union-Find

  • boruvka($N$, $f$):= $N$ 頂点のグラフについて、最小全域木を求める。$f$ は、第一引数が連結成分の個数、第二引数がそれぞれの頂点が所属する連結成分の番号が渡されて、それぞれの連結成分について他の連結成分を結ぶ重みが最小の辺を返す関数である。
template< typename T, typename F >
T boruvka(int N, F f) {
  vector< int > rev(N), belong(N);
  UnionFind uf(N);
  T ret = T();
  while(uf.size(0) != N) {
    int ptr = 0;
    for(int i = 0; i < N; i++) {
      if(uf.find(i) == i) {
        belong[i] = ptr++;
        rev[belong[i]] = i;
      }
    }
    for(int i = 0; i < N; i++) {
      belong[i] = belong[uf.find(i)];
    }
    auto v = f(ptr, belong);
    bool update = false;
    for(int i = 0; i < ptr; i++) {
      if(~v[i].second && uf.unite(rev[i], rev[v[i].second])) {
        ret += v[i].first;
        update = true;
      }
    }
    if(!update) return -1; // notice!!
  }
  return ret;
}

検証

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 "../../structure/union-find.cpp"

#include "../boruvka.cpp"

int main() {
  int V, E;
  cin >> V >> E;
  Edges< int > g;
  for(int i = 0; i < E; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    g.emplace_back(x, y, z);
  }
  const int INF = 1 << 30;
  auto f = [&](int sz, vector< int > belong) {
    vector< pair< int, int > > ret(sz, {INF, -1});
    for(auto &e : g) {
      if(belong[e.src] == belong[e.to]) continue;
      ret[belong[e.src]] = min(ret[belong[e.src]], make_pair(e.cost, belong[e.to]));
      ret[belong[e.to]] = min(ret[belong[e.to]], make_pair(e.cost, belong[e.src]));
    }
    return ret;
  };
  cout << boruvka< int, decltype(f) >(V, f) << endl;
}