最小全域木 (プリム法・クラスカル法)

導入

グラフ上の全ての頂点を含む木を全域木といいます。
グラフに重みがある場合においてそのコストが最小となるような全域木を最小全域木といいます。
辺に向きがある場合は有向最小全域木というものを構築する必要がありますが、私はこれを実装できません。どんなものか勉強したこともないです。

ここでは最小全域木を求めるために使用されるアルゴリズムのうち、使用頻度の多いプリム法とクラスカル法について解説していきます。

単純な問題ならABCのC,Dあたりで使用するイメージがあります。

先にざっくりと両者の概要を書いておきます。

プリム法
時間計算量： $O((V+E)\log{E})$

スタート地点を決める
今見終わった頂点から伸びる辺のうち一番コストの低いものを閉路ができないように選ぶ
上記を繰り返し全ての頂点が含まれれば終了

クラスカル法
時間計算量： $O(E\log{E})$

グラフ上で一番コストの低い辺を見る
その辺を追加することで閉路ができないならば追加する
全ての頂点が含まれれば終了

プリム法はunion findに似ていますね。
実際はクラスカル法で閉路の検出にunion findを使用するのですが。

プリム法

プリム法では性質上閉路が生成されないのでunion findをする必要がありません。
見ている辺の先が確定済みの頂点であるならばその辺は使用しなければいいからです。

問題
とある街には $N$ 個の建物と $M$ 本の道路がある。
各道路は2つの建物を結んでおり、それぞれ工事費用が設定されている。
あなたは全ての建物を電線で繋げるネットワークを構築したい。
電線は道路に沿って敷設でき、全ての建物が直接または間接的に繋がっていればよい。
全ての建物を繋ぐための電線敷設の最小総費用を求めよ。
なお、与えられるグラフは必ず連結であることが保証される。

入力形式
$N, M$
$u_1, v_1, w_1$
$u_2, v_2, w_2$
$. . .$
$u_M, v_M, w_M$

1行目: 建物の数 $N$ と道路の数 $M$
続く $M$ 行: 道路 $i$ は建物 $u_i$ と建物 $v_i$ を結び、費用は $w_i$

出力形式
最小総費用を1行に出力せよ。

制約

$2 \leq N \leq 10^5$

$N-1 \leq M \leq \min\left(\frac{N(N-1)}{2},\ 2 \times 10^5\right)$

$1 \leq u_i, v_i \leq N$

$u_i \neq v_i$

$1 \leq w_i \leq 10^9$

同じ2頂点間に複数の辺が存在してもよい（多重辺あり）

グラフは連結

int main(){
  int n,m;
  cin>>n>>m;
  vector<vector<pair<int,int>>> g(n);
  int u,v,w;
  for(int i=0;i<m;i++){
    cin>>u>>v>>w;
    u--;
    v--;
    g[u].push_back({v,w});
    g[v].push_back({u,w});
  }
  set<int> st; //訪問済みの頂点を入れます vector<bool>でもいいです
  //priority_queueは, {w,u,v}の順で持つと勝手にコストが小さい順(wについて昇順)になります
  priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
  pq.push({0,0,0}); //コスト0で0から0へ移動
  int ans=0;
  while(!pq.empty()){
    auto[w,u,v]=pq.top(); //最近twitterで流れてきてこの書き方知りました..
    pq.pop();
    if(st.count(u)) continue;
    st.insert(u);
    ans+=w;
    for(auto [next, cost]: g[u]){
      if(!st.count(next)) pq.push({cost,u,next});
    }
  }
  cout<<ans<<endl;
}

クラスカル法

最小コストの辺から順に見ていくだけなので、最初にsortをしましょう。
閉路の検出にunion findを使用しますが、こちらの解説は省きます。
必要ならこちらの記事などから解説を見てみてください。
以下に実装例を書きますが、私のクセも入っているので好きなようにいじってください。

問題
王国には $N$ 個の都市と $M$ 本の道路がある。
道路 $i$ は都市 $U_i$ と都市 $V_i$ を結び、整備コスト $W_i$ がかかる。

王はすべての都市を連結するために、いくつかの道路を整備したい。
整備する道路の合計コストを最小化せよ。

入力形式
$N, M$
$U_1, V_1, W_1$
$U_2, V_2, W_2$
$. . .$
$U_M, V_M, W_M$

出力形式
最小コストの合計を1行で出力せよ。

制約

$2 \leq N \leq 10^5$

$N-1 \leq M \leq 2 \times 10^5$

$1 \leq U_i, V_i \leq N$

$U_i \neq V_i$

$1 \leq W_i \leq 10^9$

与えられるグラフは連結であることが保証される

自己ループ・多重辺なし

struct UnionFind {
  vector<int> par, rank;
  UnionFind(int n) : par(n), rank(n, 0){
    for(int i=0;i<n;i++) par[i]=i;
  }
  int findRoot(int x){
    if(par[x]!=x) par[x]=findRoot(par[x]);
    return par[x];
  }
  bool same(int x, int y){
    return findRoot(x)==findRoot(y);
  }
  bool unite(int x, int y){
    x=findRoot(x);
    y=findRoot(y);
    if(x==y) return false;
    if(rank[x]<rank[y]) swap(x,y);
    par[y]=x;
    if(rank[x]==rank[y]) rank[x]++;
    return true;
  }
};

int main(){
  int n, m;
  cin>>n>>m;
  vector<tuple<int,int,int>> g(m);
  int u,v,w;
  for(int i=0;i<m;i++){
    cin>>u>>v>>w;
    g[i]={w,u,v};
  }
  sort(g.begin(),g.end());
  UnionFind uf(n);
  int ans=0;
  for(auto [w,u,v]: g){
    if(uf.unite(u,v)){
      ans+=w;
    }
  }
  cout<<ans<<endl;
}

最後に

プリム法とクラスカル法どっちが優れてる?という議論はよく見かけますが(例えばここ)、私にはわかりません。
私は特にunion findをライブラリにしているとかではないですが、クラスカル法しか使わないです。
名前が気に入った法を使うとかでもいいと思います。