ホーム > libalgo

最小全域木 (Prim)

概要

プリム法は無向グラフの最小全域木を構築するアルゴリズムです. まず適当な頂点 $r$ を選び,それのみからなる集合 $S = \{ r \}$ を用意します.次に,$S$ から $S$ の外へ伸びる辺のなかで最も重みが小さいもので結ばれている頂点を $S$ に追加します.これを $r$ から到達可能な頂点が全て $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);
}

検証

AOJ GLP6A (Submission)