クラスカル法

無向グラフを、辺の始点と終点とコストを表現したpair<pair<int,int>,long long>のvectorとして与える。

すると、コストの和が最小になるような全域木を一つ構成し、その木を構成する辺をvectorとして返す

辺がつなぐ\(2\)頂点が連結かどうかをUnionFindを用いて判定している

計算量は\(Ο(ElogE)\)

github

class Kruskal{
    // Copyright (c) 2023 0214sh7
    // https://github.com/0214sh7/library/
    private:
    int V=0,E=0;
    typedef std::pair<std::pair<int,int>,long long> P;
    std::vector<int> UF,rank;
    std::vector<std::pair<std::pair<int,int>,long long>> es;
    
    bool comp(P F,P G){
        return F.second<G.second;
    }
    
    int root(int k){
        if(UF[k]==k){
            return k;
        }else{
            UF[k]=root(UF[k]);
            return UF[k];
        }
    }
    
    bool same(int p,int q){
        return root(p)==root(q);
    }
    
    void unite(int P,int Q){
        int p=root(P);
        int q=root(Q);
        if(p==q)return;
        if(rank[p]<rank[q])std::swap(p,q);
        UF[q]=p;
        if(rank[p]==rank[q])rank[p]++;
    }
    
    public:
    
    std::vector<P> solve(std::vector<P> edge){
        //頂点数を決定する
        V=0;
        for(int i=0;i<edge.size();i++){
            V=std::max(V,edge[i].first.first+1);
            V=std::max(V,edge[i].first.second+1);
        }
        //辺数をもとめる　
        E=edge.size();
        //unionfindを初期化する
        UF.clear();
        rank.clear();
        for(int i=0;i<V;i++){
            UF.push_back(i);
            rank.push_back(0);
        }
        //辺をソートして代入しておく
        std::sort(edge.begin(),edge.end(),[&](P x, P y){return comp(x, y);});
        es=edge;
        
        std::vector<P> R;
        for(int i=0;i<E;i++){
            if(!same(es[i].first.first,es[i].first.second)){
                unite(es[i].first.first,es[i].first.second);
                R.push_back(es[i]);
            }
        }
        return R;
    }
    
};

使用例

---

実行コード

#include <bits/stdc++.h>

class Kruskal{/*省略*/};

int main(void){
    
    std::vector<std::pair<std::pair<int,int>,long long>> E;
    int N = 5;
    E.push_back({ {0,1},1});
    E.push_back({ {1,2},2});
    E.push_back({ {2,3},4});
    E.push_back({ {2,4},8});
    E.push_back({ {3,4},10000});
    
    Kruskal kruskal;
    std::vector<std::pair<std::pair<int,int>,long long>> K = kruskal.solve(E);
    
    for(int i=0;i<K.size();i++){
        std::cout << K[i].first.first << " " << K[i].first.second;
        std::cout << "  " << K[i].second << std::endl;
    }
    std::cout << std::endl;
    
    return 0;
}

出力

0 1  1
1 2  2
2 3  4
2 4  8

更新履歴

---

日時	内容
2023/06/29	ライセンスのコメントアウトを変更
2021/03/25	使用例を追加
2021/03/25	コメントを削除
2020/04/05	クラスカル法を追加