最小全域木

01 / 共通の仕組み

最小全域木は、重み付き無向グラフの全頂点を最も安く繋ぐ方法 —辺はちょうど N − 1 本、閉路なし、総重量最小。 古典的な作り方は 2 つ:Kruskal は辺を重み昇順に走査し、 Union-Find で閉路を作る辺を弾く;Prim はある頂点から始めて、 最小ヒープで現在の木に接する最も軽い辺を取り込み続ける。

01 / 一文での本質
辺を重み昇順にソートし、順番に走査して両端点が異なる成分にある辺だけを採用する(Union-Find で判定); 残りは閉路を作るのでスキップ。N − 1 本採用したら終了。
問題Union-Find で最小全域木を構築V6E8
43124265012345重み順の辺リスト辺 · w0 — 140 — 231 — 211 — 322 — 343 — 424 — 563 — 55
グラフ:ノード 6 個、辺 8 本。全域木に必要な辺は 5 本。
ステップ
0 / 16
採用済み
0 / 5
総重み
—
0 / 16

02 / パターンの骨格

# 入力:V 個のノード、edges = [(u, v, w), …]sort(edges) by w ascparent[i] ← i # DSU 初期化mst ← []; total ← 0for (u, v, w) in edges:if find(u) ≠ find(v): # 両端は別成分union(u, v); mst.push((u, v, w)); total += wif len(mst) == V − 1: break# それ以外:u, v は既に連結 → スキップ(閉路になる)return total if len(mst) == V − 1 else ∞ # 非連結

03 / このパターンを使うべき合図

「最小全域木」
典型的な言い回し。重み付き無向グラフを与えられて「全ノードを連結する最も安い部分グラフ」を求めるなら、 それは MST。入力が辺リストの形なら Kruskal が第一候補。
「全ノードを最安で連結」
LC 1135(都市を最小費用で接続)。すべての都市を連結する費用は MST の総重みに等しい。 連結コストをソートし Kruskal を流して合計を返す —— 採用辺が N − 1 に満たなければ −1。
「2 番目の MST」
LC 1489(クリティカル辺と擬クリティカル辺)。まず MST を一度求め、各辺について問う: この辺を強制除外しても同じ総重みに到達できるか?強制包含では? 各辺で Kruskal を 2 回流せば、辺をクリティカル / 擬クリティカル / それ以外にきれいに分類できる。
「全点を結ぶ最小コスト」
LC 1584。完全グラフ(全ペア間のマンハッタン距離)を作り、O(N²) 本の辺をソートして Kruskal。 密グラフでは Kruskal の辺中心方式と Prim の隣接リスト方式を比較する場 —— ここでは通常 Prim + ヒープのほうが速い。

04 / よくある落とし穴

i.
N − 1 本で打ち切るのを忘れる。
N − 1 本採用した時点で木は完成 —— 走査を続けても無駄な find / union が増えるだけ。 さらに「辺コストが純粋な加算ではない」変種(予算制約、独自タイブレーク)では、 余分な反復が静かに誤答を生む。早めに break すること。
ii.
Union-Find で経路圧縮を入れない。
Kruskal の時間はソートの O(E log E) が支配する —— 前提は find / union がほぼ定数であること。 経路圧縮(やランクによる併合)を省くと、長いチェーンで find が O(N) まで劣化し、 全体は O(E · N) に。DSU の最適化は飾りではなく、骨組みそのもの。
iii.
MST と最短経路の混同。
どちらも「最小」を扱うグラフアルゴリズムだが、最小化する対象が違う。 MST は全域木の総重みを、最短経路はある 2 点間の経路重みを最小化する。 MST 上で 2 点を結ぶ辺は、その 2 点間の最短経路とは限らない。問題が違えば不変量も違い、アルゴリズムも違う。

05 / LeetCode で練習

4 問。最初の 2 問は Kruskal の素直な練習。全点を結ぶ最小費用は密グラフのケースで、 Kruskal と Prim を比較する場。クリティカル辺は Kruskal を部品として使う —— アルゴリズムが原語になる。

01Connecting Cities With Minimum Cost— LC 1135中級→02Min Cost to Connect All Points— LC 1584中級→03Optimize Water Distribution in a Village— LC 1168難しい→04Find Critical and Pseudo-Critical Edges in MST— LC 1489難しい→

— / どれをいつ使うか

Kruskal
グラフが辺リストで与えられ、すでに Union-Find に頼っているとき。 辺を重み順にソートし、両端点が異なる成分ならその辺を採用する。辺中心で、隣接情報は要らない。
辺リスト + Union-Find · LC 1135 · LC 1489
Prim
グラフが隣接リストで与えられるか、辺数が N² に近い密グラフのとき。 任意の頂点から始め、その出辺を最小ヒープに入れて、未訪問の頂点に至る最も軽い辺を取り出し続ける。頂点中心で、木は種から育つ。
隣接リスト + 最小ヒープ · LC 1168 · LC 1584