Kruskal - クラスカル法
(Library/Graph/Kruskal.hpp)

View this file on GitHub
Last update: 2026-02-13 15:23:31+09:00
Include: #include "Library/Graph/Kruskal.hpp"

Kruskal - クラスカル法

頂点数 $V$ 辺数 $E$ の無向連結グラフの最小全域木をクラスカル法により求めます。

辺を重みの小さい順にソートし、Union-Find を用いて閉路を作らないように辺を追加していきます。

Function

Constructor

Kruskal(Graph<WeightType> &graph)

頂点数 $V$ 辺数 $E$ の無向連結グラフ $G$ を graph で初期化し、$G$ の最小全域木をクラスカル法により構築します。
$G$ が無向グラフでない場合や、連結でない場合の挙動は未定義です。

制約

$G$ は無向グラフ
$G$ は連結

計算量

$\textrm{O}(E \log E)$

GetEdgeSet

vector<Edge<WeightType>> &GetEdgeSet()

最小全域木を構成する辺集合を返します。

計算量

$\textrm{O}(1)$

GetCost

WeightType GetCost() const

最小全域木の総コスト(辺の重みの総和)を返します。

計算量

$\textrm{O}(1)$

Depends on

Verified with

verify/LC-MinimumSpanningTree.test.cpp

Code

#include "Graph.hpp"
#include "GraphMisc.hpp"
#include "../DataStructure/UnionFind.hpp"

template<typename WeightType>
class Kruskal{
    public:
    Kruskal(Graph<WeightType> &graph) : G(graph), cost_(0){
        int V = G.VertexSize();
        auto Es = ConvertEdgeSet(G);
        sort(Es.begin(), Es.end());
        UnionFind uf(V);
        for(const Edge<WeightType> &e : Es){
            if(uf.Unite(e.from, e.to)){
                cost_ += e.cost;
                edges_.push_back(e);
            }
        }
    }

    inline vector<Edge<WeightType>> &GetEdgeSet(){
        return edges_;
    }

    inline WeightType GetCost() const {
        return cost_;
    }

    private:
    Graph<WeightType> &G;
    vector<Edge<WeightType>> edges_;
    WeightType cost_;
};

#line 2 "Library/Graph/Graph.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/Graph/Graph.hpp"

using Vertex = int;

template<typename WeightType = int32_t>
struct Edge{
    public:
    Edge() = default;

    Edge(Vertex from_, Vertex to_, WeightType weight_ = 1, int idx_ = -1) :
        from(from_), to(to_), cost(weight_), idx(idx_){}
    
    bool operator<(const Edge<WeightType> &e) const {return cost < e.cost;}

    operator int() const {return to;}

    Vertex from, to;
    WeightType cost;
    int idx;
};

template<typename WeightType = int32_t>
class Graph{
    public:
    Graph() = default;

    Graph(int V) : edge_size_(0), adjacent_list_(V){}
    
    inline void AddUndirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
        adjacent_list_[v].push_back(Edge<WeightType>(v, u, w, idx));
    }
    
    inline void AddDirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
    }

    inline size_t VertexSize() const {
        return adjacent_list_.size();
    }

    inline size_t EdgeSize() const {
        return edge_size_;
    }

    inline vector<Edge<WeightType>> &operator[](const Vertex v){
        return adjacent_list_[v];
    }

    inline const vector<Edge<WeightType>> &operator[](const Vertex v) const {
        return adjacent_list_[v];
    }
    
    private:
    size_t edge_size_;
    vector<vector<Edge<WeightType>>> adjacent_list_;
};

template<typename WeightType = int32_t>
Graph<WeightType> InputGraph(int N, int M, int padding = -1, bool weighted = false, bool directed = false){
    Graph<WeightType> G(N);
    for(int i = 0; i < M; ++i){
        Vertex u, v; WeightType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        if(directed) G.AddDirectedEdge(u, v, w);
        else G.AddUndirectedEdge(u, v, w);
    }
    return G;
}
#line 2 "Library/Graph/GraphMisc.hpp"

#line 4 "Library/Graph/GraphMisc.hpp"

template<typename WeightType>
vector<Edge<WeightType>> ConvertEdgeSet(const Graph<WeightType> &G){
    vector<Edge<WeightType>> ret;
    vector<bool> check(G.EdgeSize(), false);
    int n = G.VertexSize();
    for(int u = 0; u < n; ++u){
        for(const Edge<WeightType> &e : G[u]){
            if(check[e.idx]) continue;
            check[e.idx] = true;
            ret.push_back(e);
        }
    }
    return ret;
}

template<typename WeightType>
vector<vector<WeightType>> ConvertDistanceMatrix(const Graph<WeightType> &G){
    int n = G.VertexSize();
    vector<vector<WeightType>> ret(n, vector<WeightType>(n, WeightType(INF)));
    for(int u = 0; u < n; ++u){
        ret[u][u] = WeightType(0);
        for(const Edge<WeightType> &e : G[u]){
            ret[u][e.to] = e.cost;
        }
    }
    return ret;
}

template<typename WeightType>
Graph<WeightType> ReverseGraph(const Graph<WeightType> &G){
    int n = G.VertexSize();
    Graph<WeightType> ret(n);
    for(int u = 0; u < n; ++u){
        for(const Edge<WeightType> &e : G[u]){
            ret.AddDirectedEdge(e.to, e.from, e.cost);
        }
    }
    return ret;
}
#line 2 "Library/DataStructure/UnionFind.hpp"

#line 4 "Library/DataStructure/UnionFind.hpp"

class UnionFind{
    public:
    UnionFind(size_t n) : data_(n, -1){}

    int Find(const int k){
        if(data_[k] < 0) return k;
        int r = Find(data_[k]);
        return data_[k] = r;
    }

    bool Same(const int x, const int y){
        return Find(x) == Find(y);
    }

    bool Unite(int x, int y){
        x = Find(x), y = Find(y);
        if(x == y) return false;
        if(data_[x] > data_[y]) swap(x, y);
        data_[x] += data_[y];
        data_[y] = x;
        return true;
    }
    
    size_t Size(int k){
        int v = Find(k);
        return -data_[v];
    }

    vector<vector<int>> Group(){
        vector<vector<int>> ret(data_.size());
        for(int i = 0; i < data_.size(); ++i){
            ret[Find(i)].emplace_back(i);
        }
        ret.erase(remove_if(begin(ret), end(ret), [&](vector<int> &v){
            return v.empty();
        }), end(ret));
        return ret;
    }

    private:
    vector<int> data_;
};
#line 4 "Library/Graph/Kruskal.hpp"

template<typename WeightType>
class Kruskal{
    public:
    Kruskal(Graph<WeightType> &graph) : G(graph), cost_(0){
        int V = G.VertexSize();
        auto Es = ConvertEdgeSet(G);
        sort(Es.begin(), Es.end());
        UnionFind uf(V);
        for(const Edge<WeightType> &e : Es){
            if(uf.Unite(e.from, e.to)){
                cost_ += e.cost;
                edges_.push_back(e);
            }
        }
    }

    inline vector<Edge<WeightType>> &GetEdgeSet(){
        return edges_;
    }

    inline WeightType GetCost() const {
        return cost_;
    }

    private:
    Graph<WeightType> &G;
    vector<Edge<WeightType>> edges_;
    WeightType cost_;
};

Kruskal - クラスカル法 (Library/Graph/Kruskal.hpp)

Kruskal - クラスカル法

Function

Constructor

GetEdgeSet

GetCost

Depends on

Verified with

Code

Kruskal - クラスカル法
(Library/Graph/Kruskal.hpp)