最小全域木

最小全域木（MST）は、連結な無向重み付きグラフで、全頂点をつなぐ辺の総重みを最小にする。閉路を持たず、V 頂点に対してちょうど V - 1 辺を使う。

最短経路とは目的が違う。最短経路は一つの始点から各地点への最小コストを求め、MST は全頂点をつなぐネットワーク全体のコストを最小化する。完成した木の二頂点間の経路は、元のグラフでの最短経路とは限らない。

本レッスンは同じグラフで二つの貪欲法を比べる。Prim 法は一つの連結な木を育て、毎回その内外を分けるカットを横切る辺を選ぶ。Kruskal 法は各頂点を独立した成分として始め、軽い辺から調べ、異なる成分をつなぐ場合だけ採用する。

二つのアルゴリズムの仕組み

Prim 法は木に入った頂点を集合 S、境界の辺を最小ヒープに持つ。登録時の候補辺は片端が S、もう片端が外にある。最も軽い辺を取り出し、外側の端点がまだ外なら採用して頂点を加える。待っている間に両端が木へ入っていれば、古い項目として拒否する。

左側の表示はカットの両側 S と V - S を示す。カットの性質により、そこを横切る最軽量辺は、現在の選択と両立する MST に安全に追加できる。Prim 法は頂点を加えるたびに、新しいカットでこの性質を使う。

Kruskal 法は全辺を一度整列し、採用済みの辺で両端がつながっているかを Union-Find で調べる。根が違えば採用して併合する。同じ根なら既存経路でつながっており、追加すると閉路になるため拒否する。

両手法とも負の重みを許す。負辺は優先度の高い候補だが、連結と閉路なしの条件を満たす必要がある。非負重みを要求する Dijkstra 法とは異なる。

最小全域木を作るステップ

既定の橋渡しプリセットは A–F の六頂点で、無向辺は B–C (1)、B–D (2)、C–D (3)、C–E (4)、D–F (5)、D–E (6)、A–C (7)、A–B (8)、E–F (9)。

Prim 法は A から始める。

1. A を S に入れ、A–C (7) と A–B (8) を候補にする。
2. A–C (7) はカットを横切るので採用し、C を加える。総重み 7。C–B (1)、C–D (3)、C–E (4) が加わる。
3. C–B (1) を採用し、B を加える。総重み 8。B–D (2) を追加する。
4. B–D (2) を採用し、D を加える。総重み 10。D–F (5) と D–E (6) を追加する。
5. C–D (3) を取り出す。C と D は C–B、B–D でつながっているので、閉路を防ぐため拒否する。
6. C–E (4) を採用し、E を加える。総重み 14。E–F (9) を追加する。
7. D–F (5) を採用し、F を加える。総重み 19。
8. 6 - 1 = 5 辺を採用したので完成して停止する。安全な選択で既に MST ができており、残る候補を処理する必要はない。

採用辺は A–C、B–C、B–D、C–E、D–F で、総重みは 19。

Kruskal 法は B–C (1)、B–D (2) を採用し、同一成分内の C–D (3) を拒否する。C–E (4)、D–F (5) を採用し、閉路を作る D–E (6) を拒否する。最後に A–C (7) で A をつなぎ、五辺、総重み 19 となる。

Prim 法は一つの木の現在のカットに制約されるが、Kruskal 法はグラフのどこでも成分をつなげる。そのため順序は違う。このグラフは全ての辺の重みが異なり MST が一意なので、完成形は同じになる。

時間計算量と空間計算量

隣接リストと二分最小ヒープを使う Prim 法は、本レッスンの単純グラフで O((V + E) log V) 時間、グラフとヒープを含めて O(V + E) 空間。遅延処理する境界ヒープは O(E) 項目を持ちうるため、厳密なヒープ操作は O(log E) だが、単純グラフでは O(log V) と書ける。

Kruskal 法の整列は O(E log E)、ランクによる併合と経路圧縮の Union-Find 操作は合計 O(E α(V)) で、実用上ほぼ線形になる。辺リストと Union-Find 配列は O(V + E) 空間。

密グラフを隣接行列で持つなら O(V²) の Prim 法も適する。疎グラフを辺リストで持つなら Kruskal 法が直接的だ。

境界ケース

• 一頂点：空の辺集合が全域木で、総重みは 0。
• 非連結グラフ：全域木はない。Prim 法は全頂点へ到達する前に候補が尽き、Kruskal 法は全辺を調べても成分が複数残る。非連結プリセットは失敗を報告し、部分的な森を MST として出さない。
• 同じ重み：異なる MST が同じ最小総重みを持ちうる。本レッスンは同重みの入力順を保ち、別の同点処理でも等しくよい木を得られる。
• 負辺も合法。負辺プリセットは重み -3 を採用し、総重み 3 で終わる。
• 多重辺：別々の候補として扱う。軽い辺が両端をつないだ後、重い平行辺は閉路を作る。
• 自己ループ：異なる成分をつなげないので無視する。

よくある間違い

1. Prim 法で全体の最軽量辺を選ぶ。両端が外の辺は現在の木を広げず、現在のカットから選ぶ必要がある。
2. Kruskal 法で端点が既出かだけを見る。両端の Union-Find の根を比べる。既出の端点でも別成分をつなげられる。
3. 全頂点が採用辺に現れたら止める。複数の成分でも全頂点を覆える。閉路を作らず、連結グラフで V - 1 辺を採用したことが完成条件になる。
4. 有向グラフへ適用する。有向の対応問題は通常、最小有向全域木と呼ばれ、異なるアルゴリズムが必要になる。
5. 負辺で Prim 法や Kruskal 法が無効になると思う。非負の制限は Dijkstra 法のものだ。
6. 非連結グラフの部分的な森を全域木として返す。最小全域森は有用だが、実際の結果に合った名前で報告する。

アニメーションの表示

Prim 法の候補行は最小値を読めるよう完全に整列して描く。実際の二分ヒープは部分順序を持ち、最小値の取り出しを保証する。Kruskal 法の行は実際に整列している。全辺の整列がアルゴリズムに含まれるためだ。

コードパネルは、グラフ、ヒープ、Union-Find が既に実装されている前提で中心処理を示す。ヒープへの挿入と成分の併合は別の場面に分け、各状態変化を確認できるようにしている。