最小全域木(Kruskal)

説明

最小全域木(全域木のうち、その辺群の重みの総和が最小になる木)を求めるアルゴリズム。Union-Findを用いて辺集合にある辺を加えて閉路を作らないか判定しながら、辺を重みが小さい順に走査する。

計算量

• $O(E \log V)$

実装例

依存ライブラリ Union-Find

• kruskal($edges$, $V$):= $V$ 頂点の重み付き辺集合 $edges$ からなる連結グラフの最小全域木を求める。

template< typename T >
T kruskal(Edges< T > &edges, int V) {
  sort(begin(edges), end(edges), [](const edge< T > &a, const edge< T > &b) {
    return (a.cost < b.cost);
  });
  UnionFind tree(V);
  T ret = 0;
  for(auto &e : edges) {
    if(tree.unite(e.src, e.to)) ret += e.cost;
  }
  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 "../kruskal.cpp"

int main() {
  int V, E;
  scanf("%d %d", &V, &E);
  Edges< int > edges;
  for(int i = 0; i < E; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    edges.emplace_back(a, b, c);
  }
  printf("%d\n", kruskal(edges, V));
}