Kruskal
(library/graph/mst/kruskal.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/graph/mst/kruskal.hpp"

Kruskal

できること

• 最小全域木（グラフ全頂点を満たす最小コスト木）を求める
• edgesは中でソートしてる
• 最小全域木の構造体
  • cost: 全域の総コスト。全域に達しない場合、INF
  • edges: 全域に達するためのvector<Edge>

計算量

$O(ElogV)$

• V: 頂点数
• E: 辺の数

使い方

vector<Edge> edges;
MinSpanTree mst = kruskal(edges, V);
mst.cost;
mst.edges;

Depends on

• 辺 (library/graph/base/edge.hpp)
• UnionFind 素集合データ構造 (library/various/union_find.hpp)

Verified with

• 最小全域木 - クラスカルのテスト (tests/graph.mst.kruskal.test.cpp)

Code

#pragma once
#include "library/graph/base/edge.hpp"
#include "library/various/union_find.hpp"
struct MinSpanTree {
    long long cost;
    vector<Edge> edges;
};
MinSpanTree kruskal(vector<Edge> edges, int v_cnt) {
    sort(edges.begin(), edges.end(),
         [](const Edge &a, const Edge &b) { return a.cost < b.cost; });
    UnionFind uf(v_cnt);
    long long total = 0ll;
    vector<Edge> es;
    for (auto &&e : edges) {
        if (uf.unite(e.from, e.to)) {
            es.emplace_back(e);
            total += e.cost;
        }
    }
    // 全域に達しない場合
    if (uf[0] < v_cnt) {
        total = INF;
    }
    return {total, es};
}

#line 2 "library/graph/base/edge.hpp"
struct Edge {
    int from, to;
    long long cost;
    int idx;
    Edge(int from, int to, long long cost = 1, int idx = -1)
        : from(from), to(to), cost(cost), idx(idx) {}
};
#line 2 "library/various/union_find.hpp"
struct UnionFind {
  private:
    vector<int> parent, size;

  public:
    UnionFind(int N) {
        parent.assign(N, -1);
        size.assign(N, 1);
    }
    int operator[](int p) { return size[find(p)]; }
    int find(int p) { return !~parent[p] ? p : (parent[p] = find(parent[p])); }
    bool unite(int a, int b) {
        int x = find(a), y = find(b);
        if (x == y) return false;
        if (size[x] > size[y]) swap(x, y);
        parent[x] = y, size[y] += size[x];
        return true;
    }
};
#line 4 "library/graph/mst/kruskal.hpp"
struct MinSpanTree {
    long long cost;
    vector<Edge> edges;
};
MinSpanTree kruskal(vector<Edge> edges, int v_cnt) {
    sort(edges.begin(), edges.end(),
         [](const Edge &a, const Edge &b) { return a.cost < b.cost; });
    UnionFind uf(v_cnt);
    long long total = 0ll;
    vector<Edge> es;
    for (auto &&e : edges) {
        if (uf.unite(e.from, e.to)) {
            es.emplace_back(e);
            total += e.cost;
        }
    }
    // 全域に達しない場合
    if (uf[0] < v_cnt) {
        total = INF;
    }
    return {total, es};
}

Back to top page