【さいしょうぜんいきぎ】
最小全域木 とは？
公開:
💡 「全員つなげて、コスト最小」を実現するグラフの最適解！
📌 このページのポイント
ひよこ 最小全域木って何を最小にするの？
ペンギン先生 グラフのすべての頂点をつなぐ辺の「重みの合計」を最小にするんだ。たとえば5つの街を道路でつなぐとき、全部の街に行けるようにしつつ建設費が一番安くなるルートを見つけるイメージだよ
ひよこ どうやって見つけるの？
ペンギン先生 有名なアルゴリズムが2つあるよ。クラスカル法は辺をコストの安い順に見て、閉路ができなければ採用していく方法。プリム法は1つの頂点から始めて、隣接する一番安い辺を選んで木を広げていく方法だよ
ひよこ 安い順に選ぶだけで本当に最小になるの？
ペンギン先生 これが「貪欲法（グリーディ）で最適解が得られる」という稀有な性質なんだ。カット定理という数学的な裏付けがあって、局所的に最良の選択を繰り返すだけで全体最適が保証されるよ
ひよこ 実際にはどんなところで使われてるの？
ひよこ クラスカル法とプリム法、どっちを使えばいいの？
ペンギン先生 辺が少ない疎グラフならクラスカル法、辺が多い密グラフならプリム法が効率的だよ。クラスカル法はUnion-Find（素集合データ構造）と組み合わせるのが定番で、計算量はO(E log E)。プリム法は優先度付きキューを使ってO(E log V)になるんだね
まとめ：ざっくりこれだけ覚えればOK！
「最小全域木」って出てきたら「全部つないで一番安い接続方法を見つけるアルゴリズム」と思えればだいたいOK！
📖 おまけ：英語の意味
「Minimum Spanning Tree（MST）」 ＝ 最小全域木
💬 Spanning（全域）はグラフの全頂点をカバーするという意味で、Tree（木）は閉路のない連結グラフのことだよ