Kruskal法（最小全域木）

重み付き無向グラフの最小全域木（MST）を求めるアルゴリズム。

辺を重みの小さい順に確認し、閉路ができない辺だけ採用する。

特徴

項目	内容
用途	最小全域木
対象	重み付き無向グラフ
計算量	O(E log E + E α(V))
空間計算量	O(V+E)
使用するデータ構造	Union Find

考え方

1. 辺を重みの昇順にソートする。
2. Union Findで頂点の連結性を管理する。
3. 両端が異なる連結成分に属する辺だけ採用する。
4. 採用した辺の重みを合計する。

最小全域木が存在する場合、採用される辺は V-1 本。

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct UnionFind {
    vector<int> p;
    UnionFind(int n) : p(n, -1) {}

    int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }

    bool merge(int a, int b) {
        a = root(a); b = root(b);
        if (a == b) return false;
        if (p[a] > p[b]) swap(a, b);
        p[a] += p[b];
        p[b] = a;
        return true;
    }
};

struct Edge {int u, v;ll w;};

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (auto& [u, v, w] : edges) cin >> u >> v >> w;

    vector<Edge> mst;
    auto kruskal = [&]() -> ll {
        sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.w < b.w;
        });

        UnionFind uf(n);
        ll cost = 0;
        for (const auto& e : edges) {
            if (!uf.merge(e.u, e.v)) continue;
            cost += e.w;
            mst.push_back(e);
        }
        return cost;
    };

    ll cost = kruskal();

    if ((int)mst.size() != n - 1) cout << "IMPOSSIBLE\n";
    else cout << cost << '\n';
}

使用例

入力（0-indexed、無向グラフ）

4 5
0 1 1
0 2 4
1 2 2
1 3 5
2 3 3

出力

6

重み1、2、3の辺を採用する。

採用した辺の取得

ll cost = kruskal();

for (auto [u, v, w] : mst) {
    cout << u << " " << v << " " << w << '\n';
}

mst には採用した辺が格納される。

注意点

• 対象は重み付き無向グラフ。
• 負の重みがあっても使用できる。
• グラフが非連結の場合、最小全域木は存在しない。
• 非連結の場合でも、最小全域森（各連結成分の最小全域木）が求まる。
• 最小全域木が存在するかは、採用した辺が V-1 本かで判定できる（V >= 1）。
• 最小全域木は一意とは限らない。
• Union Findで閉路の発生を防ぐ。
• 最小全域木は最短経路木とは異なる。

関連

• Union Find
• Prim法
• 最小全域木