Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Kruskal

コードについての説明

グラフの最小全域木の重みを求めるアルゴリズム.
最小全域木とはもとのグラフの部分グラフでありかつすべての頂点を含む木のなかで辺の重みの総和が最小のもののことである. 同じく最小全域木を求めるアルゴリズムとして Prim 法 がある.
コストの小さい辺から(閉路ができないように)貪欲に取っていくことでアルゴリズムが正しく動くことが知られている. 証明はグラフ, マトロイドの両面から示せる.
グラフの側面から示した証明はよくあるので, 次の補足でマトロイドの側面から Kruskal 法の正当性を示してみた(⇒ 補足).

(関数)
add_edge$(u, v, cost)$ : $u, v$ の間に重み $cost$ の無向辺を追加する
solve(): 最小全域木の重みを計算する

時間計算量: $\O (m \log n)$

コード

  1. class UnionFind {
  2. private:
  3.     int sz;
  4.     vector<int> par, nrank;
  5. public:
  6.     UnionFind(){}
  7.     UnionFind(int node_size) : sz(node_size), par(sz), nrank(sz, 0){
  8.         iota(par.begin(), par.end(), 0);
  9.     }
  10.     int find(int x){
  11.         if(par[x] == x) return x;
  12.         else return par[x] = find(par[x]);
  13.     }
  14.     void unite(int x,int y){
  15.         x = find(x), y = find(y);
  16.         if(x == y) return;
  17.         if(nrank[x] < nrank[y]) swap(x,y);
  18.         par[y] = x;
  19.         if(nrank[x] == nrank[y]) nrank[x]++;
  20.     }
  21.     bool same(int x,int y){
  22.         return find(x) == find(y);
  23.     }
  24. };
  25.  
  26. template<typename T> class Kruskal{
  27. public:
  28.     struct edge{
  29.         int u,v;
  30.         T cost;
  31.         bool operator<(const edge& another) const {
  32.             return cost < another.cost;
  33.         }
  34.     };
  35.     vector<edge> es;
  36.     int V;
  37.     Kruskal(int node_size) : V(node_size){}
  38.     void add_edge(int u,int v,T cost){
  39.         es.push_back((edge){u,v,cost});
  40.     }
  41.     T solve(){
  42.         UnionFind uf(V);
  43.         T res = 0;
  44.         int cnt = 0;
  45.         sort(es.begin(),es.end());
  46.         for(edge& e : es){
  47.             if(!uf.same(e.u,e.v)){
  48.                 uf.unite(e.u,e.v);
  49.                 res += e.cost;
  50.                 cnt++;
  51.                 if(cnt == V-1){
  52.                     break;
  53.                 }
  54.             }
  55.         }
  56.         return res;
  57.     }
  58. };

verify 用の問題

AOJ : Minimum Spanning Tree 提出コード