ei1333's page

ホーム > Wiki

最小全域木(Kruskal)

説明

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

使い方

Union-Find が必要

計算量

$O(E \log V)$

$V$: 頂点数, $E$: 辺数

実装例

struct edge
{
  int u, v, cost;
  bool operator<(const edge& e) const
  {
    return(cost < e.cost);
  };
};
template< class T = int >
T kruskal(vector< edge > &edges, int V)
{
  sort(edges.begin(), edges.end());
  UnionFind tree(V);
  T ret = 0;
  for(auto& e : edges) {
    if(tree.unite(e.u, e.v)) ret += e.cost;
  }
  return (ret);
}

問題例