最小全域木とは？クラスカル法とプリム法をわかりやすく解説

最小全域木が解く問題

複数の建物をケーブルで、複数の町を道路で、複数のサーバーをネットワーク回線でつなぎたいとします。接続の候補には、それぞれコストがかかります。すべての場所が（直接または間接に）つながるようにしつつ、合計コストを最小にしたいわけです。ループを作る余分な接続は不要なので、答えは木になります。V 個のノードをちょうど V − 1 本の辺で結んだものです。この木が最小全域木です。

最小全域木は最短経路木ではありません。最小化するのはすべての辺の合計の重みであり、1つの開始ノードから他のノードまでの距離ではありません。

なぜ貪欲な選択でうまくいくのか：カット性質

ノードを任意の2つのグループに分けます。2つのグループをまたぐ辺のうち最も軽い辺は、ある最小全域木に含まれます。どちらのアルゴリズムもこの事実に基づいています。

すべての辺の重みが異なれば最小全域木は一意なので、どちらのアルゴリズムも同じ木を返します。重みが等しい辺があると、合計が同じ最小全域木が複数存在することがあります。

具体例で一歩ずつ確認

5つのノードと、辺 A–B 4、A–C 3、B–C 1、B–D 2、C–D 4、D–E 2、C–E 5 を持つ無向グラフです。

クラスカル法です。辺を重みでソートします。

Aから始めるプリム法です。{A} から出る最も安い辺は A–C（3）、{A, C} からは C–B（1）、{A, B, C} からは B–D（2）、{A, B, C, D} からは D–E（2）です。同じ木になり、合計の重みは 3 + 1 + 2 + 2 = 8 です。

Pythonでのクラスカル法

Union-Findは、ノードごとに親へのポインタを持ちます。find はノードが属する連結成分の代表を返し、2つのノードは代表が同じときに限ってつながっています。

def kruskal(nodes, edges):
    parent = {n: n for n in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x

    tree, total = [], 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:                          # different components: no cycle
            parent[ru] = rv
            tree.append((u, v, w))
            total += w
    return tree, total

nodes = "ABCDE"
edges = [(4, "A", "B"), (3, "A", "C"), (1, "B", "C"), (2, "B", "D"),
         (4, "C", "D"), (2, "D", "E"), (5, "C", "E")]
print(kruskal(nodes, edges))
# ([('B', 'C', 1), ('B', 'D', 2), ('D', 'E', 2), ('A', 'C', 3)], 8)

完全なUnion-Findでは、木を浅く保つために、ランクまたはサイズによる併合も使います。経路半減だけでも、実際には十分高速です。木の辺が V − 1 本になった時点で、ループを早めに終了できます。

Pythonでのプリム法

プリム法には隣接リストが必要です。ダイクストラ法と同様に遅延削除を使います。木から出るすべての辺をプッシュし、遠い側の端点がすでに木に含まれている辺は読み飛ばします。

import heapq
from collections import defaultdict

def prim(edges, start):
    graph = defaultdict(list)
    for w, u, v in edges:
        graph[u].append((w, u, v))
        graph[v].append((w, v, u))
    in_tree = {start}
    heap = list(graph[start])
    heapq.heapify(heap)
    tree, total = [], 0
    while heap:
        w, u, v = heapq.heappop(heap)
        if v in in_tree:
            continue
        in_tree.add(v)
        tree.append((u, v, w))
        total += w
        for edge in graph[v]:
            if edge[2] not in in_tree:
                heapq.heappush(heap, edge)
    return tree, total

print(prim(edges, "A"))
# ([('A', 'C', 3), ('C', 'B', 1), ('B', 'D', 2), ('D', 'E', 2)], 8)

時間計算量と空間計算量

E は高々 V² なので、log E は高々 2 log V です。そのため、O(E log E) と O(E log V) は同じオーダーです。

バリエーションとよくある間違い

• 非連結のグラフ：全域木は存在しません。クラスカル法は最小全域森（連結成分ごとに1本の木）を返し、1つの開始ノードから始めるプリム法は、その開始ノードの連結成分だけを対象にします。木の辺が V − 1 本あるか確認してください。
• 最大全域木：辺を降順にソートします（または重みの符号を反転します）。どちらのアルゴリズムも、負の重みがあっても問題ありません。
• 有向グラフには別のアルゴリズム（最小全有向木、Chu–Liu/Edmonds）が必要です。クラスカル法とプリム法は適用できません。
• クラスタリング：クラスカル法を実行し、連結成分が k 個になった時点で止めます。結果は、k 個のグループへの単連結法クラスタリングになります。
• 1926年のボルフカ法（Borůvka）は、すべての連結成分から最も安い辺を同時に追加するもので、並列化に向いています。

使う場面と実世界での用途

• ネットワーク設計：どんな接続形態でもよい場合に、拠点間をケーブル、パイプ、道路で結ぶ最も安い方法を求める。
• 近似アルゴリズム：最小全域木から、距離が三角不等式を満たす巡回セールスマン問題の、最適解の長さの高々2倍の巡回路が得られます。
• 最小全域木の最も重い辺を切ることによる、クラスタリングや画像のセグメンテーション。
• コーディング面接の問題：すべての点を結ぶ最小コスト、最小コストで都市をつなぐ、村の水道配分の最適化。