最小全域木（MST）

重み付きの連結な無向グラフで、すべての頂点を閉路なしにつなぐ木（全域木）のうち、辺の重みの合計が最小になるもの。拠点を結ぶ通信網や配線、道路を最も安い費用で敷設する問題などに使われる。重みの小さい辺から選ぶクラスカル法と、木を1頂点ずつ広げるプリム法で求める。

最小全域木を求めるアルゴリズムの一つ。すべての辺を重みの小さい順に並べ、閉路ができない場合に限ってその辺を採用することを、頂点数－1本の辺を選ぶまで繰り返す。閉路の判定には、頂点が同じ集合に属するかを素早く調べるUnion-Find（素集合データ構造）を使い、計算量は辺の整列が支配的でO(E log E)である。

最小全域木を求めるアルゴリズムの一つ。任意の1頂点から始め、作りかけの木に含まれる頂点と含まれない頂点を結ぶ辺のうち重みが最小のものを選んで木を広げることを、すべての頂点が含まれるまで繰り返す。優先度付きキューを使うとO(E log V)で計算でき、辺の多い密なグラフに向く。