忘れがちだった最小全域木のコストを求めるアルゴリズム（クラスカル法、プリム法）をライブラリ化した

前提

いずれも発想は貪欲法である。

クラスカル法

• 実装内容の理解についてはクラスカル法の方が楽
• 頂点数に対応する大きさのUnionFind木を用意する
• グラフの辺を、重みの小さい順に見ていき、(u, v)がまだ同じグループに属していないならばその辺を採用することを繰り返す
• 上記を全ての辺について行うと最終的に最小全域木のコストが求まる
• ボトルネックは辺のソート部分のため、辺数をE、頂点数をVとして O(ElogE) と覚えておけばよい（厳密にはO(ElogV）

クラスカル法のわかりやすい解説

algo-logic.info

プリム法

• 空集合Sを作り、元の頂点集合Vから任意に1個をSに追加する
• 今集合Sから延びる辺で、Sに無い頂点へ延びる辺のうち最小のものを最小全域木の辺として採用し、その頂点をSに追加する
• ↑の処理はナイーブに実装するとO(V^2)だが、優先度キューを用いることでO(ElogV)になる
• こちらも感覚的にはO(ElogE)と覚えておけばよい
  • 全ての辺を見て優先度キューに追加する（O(ElogE)）
  • 最小コストの辺を取得する（O(logE)）

プリム法のわかりやすい解説

algo-logic.info

検証用問題

onlinejudge.u-aizu.ac.jp

以下の2つのライブラリは、コンストラクタにグラフGを与えたのち、getを呼ぶだけで良い。

実装（クラスカル法）

※ 要 UnionFind木

pione.hatenablog.com

/* UnionFind */

class Kruskal{
  private:
  long long cost=0;
  
  public:
  Kruskal(const vector<vector<pair<int, long long>>>& G){
    int n=G.size();
    vector<tuple<long long, int, int>> V;
    for(int i=0; i<n; i++){
      for(auto p: G[i]){
        int v=p.first, c=p.second;
        V.emplace_back(c,v,i);
      }
    }
    
    sort(V.begin(), V.end());
    
    UnionFind uf=UnionFind(n);
    for(auto e: V){
      long long c; int u, v; tie(c,u,v)=e;
      if(!uf.is_same(u, v)){
        cost+=c;
        uf.connect(u, v);
      }
    }
  }
  
  long long get(){
    return cost;
  }
};

実装（プリム法）

class Prim{
  private:
  long long cost=0;
  vector<bool> used;
  
  public:
  Prim(const vector<vector<pair<int,long long>>>& G, const int root=0){
    int n=G.size();
    used.resize(n);
    used[root]=1;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
    for(auto p: G[root]){
      int v=p.first; long long c=p.second;
      if(!used[v]){
        q.emplace(c, v);
      }
    }
    while(!q.empty()){
      int v; long long c; tie(c, v)=q.top(); q.pop();
      if(!used[v]){
        used[v]=1;
        cost+=c;
        for(auto p: G[v]){
          int nv=p.first; long long nc=p.second;
          if(!used[nv]){
            q.emplace(nc, nv);
          }
        }
      }
    }
  }
  
  long long get(){
    return cost;
  }
};