プリム法

プリム法とは、クラスカル法と同様に重み付き無向グラフにおいて最小全域木（とその辺の重みの総和）を求めるアルゴリズムである。

プリム法とは

1. ある頂点を一つ選ぶ。
2. 確定している頂点から確定していない頂点への辺のうち、重みが最も小さなものを通る辺としてその確定していない頂点を確定させる。
3. 2を確定していない頂点が無くなるまで続ける。

証明

貪欲法に似ていて、実際に他の方法があるとして矛盾を導くことができる。

実装

let mut used = vec![false; n];
let mut h = std::collections::BinaryHeap::new();
let mut ans = 0;

used[0] = true;
for &(i, w) in &e[0] {
    h.push((Reverse(w), i));
} 

while let Some((Reverse(w), i)) = h.pop() {
    if used[i] {
        continue;
    }
    ans += w;
    used[i] = true;

    for &(j, x) in &e[i] {
        if !used[j] {
            h.push((Reverse(x), j));
        }
    }
}

今回はansとして最小全域木の重さの合計を求めている。計算量はBinaryHeapを用いることでO(ElogE)になっている。