最小全域木
01 / 共通の仕組み
最小全域木は、重み付き無向グラフの全頂点を最も安く繋ぐ方法 —辺はちょうど N − 1 本、閉路なし、総重量最小。 古典的な作り方は 2 つ:Kruskal は辺を重み昇順に走査し、 Union-Find で閉路を作る辺を弾く;Prim はある頂点から始めて、 最小ヒープで現在の木に接する最も軽い辺を取り込み続ける。
01 / 一文での本質
全域木は種ノードから 1 本ずつ辺を吸収しながら育つ —— 毎回現在の木から未訪問ノードへ渡る最も軽い辺を取り込む。 候補となる横断辺を最小ヒープで管理し、N − 1 ラウンド回せば木が完成する。
問題重み付き無向グラフの最小全域木グラフメッシュ種0
グラフのノード数は 6。種を選び、毎ラウンド最も軽い横断辺を取り込んで木を育てる。
ステップ
0 / 7
ヒープ
—
木
0 / 6
合計
0
0 / 7
02 / パターンの骨格
# Prim の MST —— 種から木を育てるvisited ← {s}pq ← 最小ヒープ (w, s, v) for (v, w) in neighbors(s)mst ← [ ], total ← 0while pq が空でない かつ |visited| < N:(w, u, v) ← pq.pop_min() # 最も軽い横断辺if v in visited: continue # 既に木の中、スキップvisited.add(v); mst.append((u, v, w)); total += wfor (x, w') in neighbors(v): # 新しい前線を入れるif x not in visited:pq.push((w', v, x))
03 / このパターンを使うべき合図
「種ノードからの最小全域木」
重み付き無向グラフの全ノードを最も安く繋ぎたく、グラフが隣接リストで与えられている —— 任意の 1 ノードから外向きに育てる Prim はぴったり。{ノード → 隣接} という構造があれば十分。
「密グラフ(E ≈ N²)」
辺数が N × N 行列をほぼ埋めているとき、Prim が有利。二分ヒープで O(E log V)、配列 PQ なら O(V²) —— どちらも E ≈ V² 本の辺を最初からソートする Kruskal を上回る。
「ケーブル / 配管のネットワーク」
都市の接続、光ファイバ敷設、クラスタ統合 —— 「全ノードが連結、配線長の合計が最小」という問題は、 種から育てる物語が実際の配線作業にそのまま対応する。
「連結性を保つために辺を追加」
問題が「1 本ずつ辺を加える」「毎回最も安いものを選ぶ」と語るなら、 Prim の「カット - 吸収」ループのほうが Kruskal の「ソート - 統合」よりも素直に当てはまる。
04 / よくある落とし穴
i.
既訪問ノードへの辺をヒープに押し戻す。
ノードを吸収するたびにすべての出辺をヒープに入れるが、 隣接ノードの多くは既に木の中にある。
if v not in visited でガードしないと、 ヒープに古いエントリが大量に積もり、メモリも log 因子も膨らむ。 押し込み時にフィルタ(安い)、取り出し時にも古いエントリをスキップ(これも安い) —— 両方が正しく、両方が必要になることが多い。ii.
Prim と Dijkstra を取り違える。
見た目は同じ —— グラフ、最小ヒープ、visited 集合、while ループ —— しかしヒープのキーが本質的に異なる。 Dijkstra は
dist[v](始点からの累積距離)を持つ; Prim は w(カットを跨ぐ 1 本の辺の重み)だけを持つ。 取り違えると同じグラフで誤った答えを出すが、エラーは何も出ない。iii.
疎グラフに隣接行列を使う。
古典的な配列 PQ の Prim は辺数に関係なく O(V²)。 E ≈ V² なら最適だが、E ≪ V² では無駄になる。 疎グラフでは隣接リスト + 二分ヒープで O(E log V) に戻すか、 Kruskal の辺リスト + Union-Find で同じ計算量にできる。
05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。
— / どれをいつ使うか
Kruskal
グラフが辺リストで与えられ、すでに Union-Find に頼っているとき。 辺を重み順にソートし、両端点が異なる成分ならその辺を採用する。辺中心で、隣接情報は要らない。
辺リスト + Union-Find · LC 1135 · LC 1489
Prim
グラフが隣接リストで与えられるか、辺数が N² に近い密グラフのとき。 任意の頂点から始め、その出辺を最小ヒープに入れて、未訪問の頂点に至る最も軽い辺を取り出し続ける。頂点中心で、木は種から育つ。
隣接リスト + 最小ヒープ · LC 1168 · LC 1584