クラスカル法
最終更新
クラスカル法は最小全域木 (MST) を構築します。これはすべての頂点を閉路なしでつなぐ最も安価な辺の集合です。まずすべての辺を重み順にソートし、次にまだ接続されていない2つの頂点を結ぶ限り、貪欲に次に安い辺を追加していきます。上の再生ボタンを押すと、安全で安い辺が1本ずつ加わって木が成長する様子を見られます。
「すでに接続済みか?」の判定は、union-find (素集合) データ構造で行います。ある辺の両端がすでに同じ連結成分にある場合、その辺を追加すると閉路ができてしまうため、その辺はスキップされます。コストはソートが支配的で、全体で O(E log E) になります。クラスカル法は疎なグラフで真価を発揮します。
時間計算量と空間計算量
| 指標 | 計算量 | 備考 |
|---|---|---|
| 時間 | O(E log E) | 辺のソートが支配的 |
| union-find の操作 | ≈ O(E α(V)) | 経路圧縮により1回のチェックはほぼ定数時間 |
| 空間 | O(V + E) | 辺のリスト + 素集合構造 |
| 最適な対象 | 疎なグラフ | グローバルな辺リストから動作する |
ステップごとの手順
| ステップ | 何が起こるか |
|---|---|
| 1 | すべての辺を重みの昇順でソートする。 |
| 2 | 各頂点を独自の連結成分に置く (union-find)。 |
| 3 | 次に安い辺を取り出す。 |
| 4 | 両端が異なる連結成分にあれば、木に追加してそれらを併合する。 |
| 5 | そうでなければスキップする (閉路ができてしまう)。 |
| 6 | 木の辺が V − 1 本になったら停止する。 |
具体例
頂点 A, B, C, D と辺 A-B(1), B-C(2), A-C(3), C-D(4), B-D(5) を持つグラフ。ソート済みの辺: A-B(1), B-C(2), A-C(3), C-D(4), B-D(5):
| 辺 (重み) | 処理前の連結成分 | 処理 |
|---|---|---|
A-B(1) | {A} {B} {C} {D} | 異なる連結成分 - MSTに追加し、{A,B} に併合する。 |
B-C(2) | {A,B} {C} {D} | 異なる連結成分 - MSTに追加し、{A,B,C} に併合する。 |
A-C(3) | {A,B,C} {D} | A と C はすでに同じ - スキップ (閉路ができてしまう)。 |
C-D(4) | {A,B,C} {D} | 異なる連結成分 - MSTに追加し、{A,B,C,D} に併合する。 |
| 停止 | {A,B,C,D} | 木の辺が V - 1 = 3 本。MST = A-B, B-C, C-D、総重み 7。 |
クラスカル法を使うべき場面
| 使うべき場面 | 避けるべき場面 |
|---|---|
| グラフが疎である (頂点に対して辺が少ない)。 | グラフが密である - ヒープを使うプリム法の方が通常は速い。 |
| 辺がソート可能なグローバルリストとしてすでに手に入る。 | 辺が頂点ごとに走査する隣接リスト経由でしか得られない。 |
| union-find に支えられたシンプルな実装が欲しい。 | 特定の開始頂点から木を成長させる必要がある。 |
| 非連結グラフの全域森を構築したい。 | 完全なソートなしでストリームで届く辺を処理する必要がある。 |
Kruskal's Algorithmのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なKruskal's Algorithmの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのKruskal's Algorithmのコード
Python
1def find(parent, x):2 while parent[x] != x:3 parent[x] = parent[parent[x]] # path compression4 x = parent[x]5 return x6
7
8def kruskal(vertices, edges):9 # Take the cheapest edge that does not close a cycle10 parent = {v: v for v in vertices}11 mst, total = [], 012 for w, u, v in sorted(edges):13 root_u, root_v = find(parent, u), find(parent, v)14 if root_u != root_v:15 parent[root_u] = root_v16 mst.append((u, v, w))17 total += w18 return mst, total19
20
21vertices = ["A", "B", "C", "D", "E"]22edges = [23 (4, "A", "B"), (1, "A", "C"), (3, "B", "C"), (2, "B", "D"),24 (5, "C", "D"), (6, "C", "E"), (7, "D", "E"),25]26
27mst, total = kruskal(vertices, edges)28for u, v, w in mst:29 print(f"{u} - {v} (weight {w})")30print("Total MST weight:", total)JavaScriptでのKruskal's Algorithmのコード
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 4], ["A", "C", 2], ["B", "C", 1], ["B", "D", 5],4 ["C", "D", 8], ["C", "E", 10], ["D", "E", 2],5];6
7function kruskal() {8 // Union-find with path compression detects cycles cheaply9 const parent = Object.fromEntries(nodes.map((n) => [n, n]));10 const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));11 const mst = [];12 let total = 0;13 const sorted = [...edges].sort((a, b) => a[2] - b[2]);14 for (const [u, v, w] of sorted) {15 const rootU = find(u);16 const rootV = find(v);17 if (rootU !== rootV) {18 parent[rootU] = rootV;19 mst.push(`${u}-${v} (${w})`);20 total += w;21 }22 }23 return { mst, total };24}25
26const { mst, total } = kruskal();27console.log("MST edges:", mst.join(", "));28console.log("Total weight:", total);JavaでのKruskal's Algorithmのコード
Java
1import java.util.Arrays;2
3public class Main {4 static int[] parent;5
6 static int find(int x) {7 if (parent[x] != x) parent[x] = find(parent[x]); // path compression8 return parent[x];9 }10
11 static boolean union(int a, int b) {12 int rootA = find(a), rootB = find(b);13 if (rootA == rootB) return false; // would create a cycle14 parent[rootA] = rootB;15 return true;16 }17
18 public static void main(String[] args) {19 int n = 6;20 int[][] edges = {21 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},22 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}23 };24 Arrays.sort(edges, (a, b) -> a[2] - b[2]);25 parent = new int[n];26 for (int i = 0; i < n; i++) parent[i] = i;27
28 int total = 0, used = 0;29 for (int[] e : edges) {30 if (union(e[0], e[1])) {31 System.out.println("Take edge " + e[0] + "-" + e[1] + " (weight " + e[2] + ")");32 total += e[2];33 if (++used == n - 1) break;34 }35 }36 System.out.println("MST total weight: " + total);37 }38}C++でのKruskal's Algorithmのコード
C++
1#include <algorithm>2#include <iostream>3#include <numeric>4#include <vector>5
6struct Edge {7 int u, v, weight;8};9
10struct DSU {11 std::vector<int> parent;12 explicit DSU(int n) : parent(n) {13 std::iota(parent.begin(), parent.end(), 0);14 }15 int find(int x) {16 if (parent[x] != x) parent[x] = find(parent[x]); // path compression17 return parent[x];18 }19 bool unite(int a, int b) {20 int ra = find(a), rb = find(b);21 if (ra == rb) return false; // would create a cycle22 parent[ra] = rb;23 return true;24 }25};26
27int main() {28 const int n = 5;29 std::vector<Edge> edges = {30 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},31 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},32 };33 // Greedily take the cheapest edge that connects two components34 std::sort(edges.begin(), edges.end(),35 [](const Edge& a, const Edge& b) { return a.weight < b.weight; });36 DSU dsu(n);37 int total = 0;38 std::cout << "MST edges:\n";39 for (const Edge& e : edges) {40 if (dsu.unite(e.u, e.v)) {41 std::cout << " " << e.u << " - " << e.v42 << " (weight " << e.weight << ")\n";43 total += e.weight;44 }45 }46 std::cout << "Total weight: " << total << "\n";47 return 0;48}CでのKruskal's Algorithmのコード
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5#define N 56
7typedef struct {8 int u, v, weight;9} Edge;10
11int parent[N];12
13int find(int x) {14 if (parent[x] != x) parent[x] = find(parent[x]); // path compression15 return parent[x];16}17
18bool unite(int a, int b) {19 int ra = find(a), rb = find(b);20 if (ra == rb) return false; // would create a cycle21 parent[ra] = rb;22 return true;23}24
25int cmpEdge(const void* a, const void* b) {26 return ((const Edge*)a)->weight - ((const Edge*)b)->weight;27}28
29int main(void) {30 Edge edges[] = {31 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},32 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},33 };34 int m = sizeof(edges) / sizeof(edges[0]);35 for (int i = 0; i < N; i++) parent[i] = i;36 // Greedily take the cheapest edge that connects two components37 qsort(edges, m, sizeof(Edge), cmpEdge);38 int total = 0;39 printf("MST edges:\n");40 for (int i = 0; i < m; i++) {41 if (unite(edges[i].u, edges[i].v)) {42 printf(" %d - %d (weight %d)\n",43 edges[i].u, edges[i].v, edges[i].weight);44 total += edges[i].weight;45 }46 }47 printf("Total weight: %d\n", total);48 return 0;49}クラスカル法のよくある質問
最小全域木とは何ですか?
連結な重み付きグラフの最小全域木 (MST) とは、すべての頂点を閉路なしで、可能な限り小さい総重みでつなぐ辺の部分集合です。頂点が
V 個のとき、辺はちょうど V - 1 本になります。クラスカル法とプリム法の違いは何ですか?
どちらも貪欲に最小全域木を構築します。クラスカル法はすべての辺をグローバルにソートし、union-find を使って閉路を作らない最も安い辺を追加します。プリム法は開始頂点から1本の木を外へ成長させ、常に木から出ていく最も安い辺を追加します。クラスカル法は疎なグラフに、プリム法 (ヒープ付き) は密なグラフに向いています。
クラスカル法はなぜ union-find を使うのですか?
辺を追加する前に、クラスカル法はその両端がすでに接続されているかを確認しなければなりません。そのような辺を追加すると閉路ができるからです。union-find (素集合) は「同じ連結成分にあるか?」に答え、ほぼ定数の償却時間で連結成分を併合するため、アルゴリズムを効率的に保ちます。
プリム法ではなくクラスカル法を使うべきなのはいつですか?
グラフが疎で、すべての辺をソート可能なリストとしてすでに持っている場合はクラスカル法を選びましょう。
E が小さければ O(E log E) のソートは安価です。二分ヒープやフィボナッチヒープを使うプリム法は、E が V² に近づく密なグラフで有利になる傾向があります。すべての辺を事前にソートせずに済むためです。クラスカル法は非連結グラフでも動作しますか?
はい。グラフが非連結の場合、クラスカル法は単に
V - 1 本の辺に到達できず、代わりに最小全域森 (連結成分ごとに1つの MST) を生成します。union-find が経路のない頂点同士を決して併合しないため、これは自然に得られます。クラスカル法を実装する際の最もよくある間違いは何ですか?
union-find の経路圧縮とランクによる併合を省くことで、各連結判定がほぼ定数からほぼ線形に落ち、実行時間を支配してしまうことがあります。もう1つのよくあるバグは、辺を追加した後に2つの連結成分を実際に併合し忘れることで、これにより後続の辺が閉路を作れてしまいます。
関連リソース
その他の可視化
