最小全域木
正式名称
Minimum Spanning Tree（MST）
一言でいうと
全頂点を最も低い総コストでつなぐ木
初心者向け説明
最小全域木とは、重み付きグラフですべての頂点をつなぎながら、選んだ辺の重みの合計を最小にした全域木です。
例えば複数の拠点をケーブルで接続するとき、
全拠点を接続しながら、ケーブルの総距離を最小にしたい
といった問題として考えることができます。
ポイント
- すべての頂点をつなぐ
- 閉路を持たない
- 重みの合計を最小にする
- 最短経路とは目的が異なる
関連用語
関連記事
- グラフ理論とは？サイクリックグラフや重み付きグラフを基礎から理解しよう
🍯 はちみつメモ
最小全域木 = 全員をできるだけ安くつなぐ