最小全域木 (Prim)
概要
プリム法は無向グラフの最小全域木を構築するアルゴリズムです．
まず適当な頂点 $v$ を選び，集合 $S = \{ v \}$ を用意します． 次に，$S$ から $S$ の外へ伸びる辺のなかで最も重みが小さいもので結ばれている頂点 $w$ を $S$ に追加します ($S \gets S \cup \{w\}$)．これを $v$ から到達可能な頂点が全て $S$ に覆われるまで繰り返します．
同じ目的を達成するクラスカル法 (graph/kruskal.cc) というアルゴリズムもあります．ただし，グラフが非連結な場合の結果が異なります．
計算量
$O(E \log V)$
使い方
連結でないなら $r$ から到達不可能な点は無視する．
実装
bool operator<(const Edge &e, const Edge &f) { return e.weight > f.weight; }
std::pair<Weight, Edges> prim(const Graph &g, int r = 0) {
Edges T;
Weight total = 0;
std::vector<int> vis(g.size());
std::priority_queue<Edge> q;
q.emplace(-1, r, 0);
while (q.size()) {
Edge e = q.top();
q.pop();
if (vis[e.dst]) continue;
vis[e.dst] = true;
total += e.weight;
if (e.src != -1) T.emplace_back(e);
for (auto &f : g[e.dst])
if (!vis[f.dst]) q.emplace(f);
}
return std::make_pair(total, T);
}