データ構造入門：最小全域木（Minimum Spanning Tree）とは

全域木（スパニングツリー）とは

全域木（スパニングツリー）とは、無向グラフの部分集合であり、グラフ内のすべての頂点を最小限の数の辺で接続した木構造のことを指します。

グラフ内のすべての頂点が互いに連結されている場合、必ず少なくとも1つの全域木が存在します。また、1つのグラフに対して、複数の全域木が存在することもあります。

最小全域木（MST）とは

最小全域木（Minimum Spanning Tree：MST）とは、連結された重み付き無向グラフにおいて、すべての頂点を接続しながら、辺の重みの合計が最小となるような辺の部分集合です。

MSTを求めるアルゴリズムとしては、プリム法（Prim's algorithm）やクラスカル法（Kruskal's algorithm）が代表的です。本章では、これらの中でもプリム法について詳しく解説していきます。

全域木の条件

前述のとおり、1つのグラフには複数の全域木が存在する可能性があります。ここで重要なのは、頂点の数が n 個であるとき、全域木は必ず n − 1 本の辺を持つという点です。

さらに、グラフの各辺に重み（コスト）が割り当てられており、かつ複数の全域木が存在する場合、その中から合計コストが最小となる全域木、すなわち最小全域木を見つけ出す必要があります。

なお、同じ重みを持つ辺（重複した重みの辺）がグラフ内に存在する場合は、複数の異なる最小全域木が存在することもあります。

具体例

上図のグラフでは、一つの全域木を示しています。ただし、これは最小全域木ではありません。この全域木の総コストは以下のように計算できます。

(5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38

このように、同じグラフでも辺の選び方によって総コストは変化するため、最小のコストで全頂点を接続できる組み合わせを見つけることが、最小全域木問題の本質となります。