最小全域木 (Kruskal)
概要
クラスカル法は無向グラフの最小全域木を構築するアルゴリズムです．
すべての辺を重みの昇順でソートした列を es を作り，前から順に閉路ができないなら追加していきます．
閉路ができるかの判定には Union-Find 木 (data-structure/union-find.cc) 使います．
私の実装では，プリム法 (graph/prim.cc) とクラスカル法の違いは最初に選んだ頂点から到達不可能な頂点が存在したときに無視するか森ができるかどうかです．
計算量
$O(E \alpha(E))$ : $\alpha(x)$ はアッカーマン関数の逆関数
使い方
連結でないなら森ができる．
実装
//@require ../data-structure/union-find.cc
std::pair<Weight, Edges> kruskal(Graph const &g) {
uf_tree uf(g.size());
Edges es;
for (auto &adj : g)
for (auto &e : adj) es.emplace_back(e);
std::sort(es.begin(), es.end(),
[](const Edge &e, const Edge &f) { return e.weight < f.weight; });
Weight total = 0;
Edges T;
for (auto &e : es)
if (!uf.is_same(e.src, e.dst)) {
T.push_back(e);
total += e.weight;
uf.unite(e.src, e.dst);
}
return std::make_pair(total, T);
}