MST（最小全域木）

重み付きの連結グラフのすべての頂点を、閉路を作らずに結ぶ木（全域木）のうち、辺の重みの合計が最小になるもの。重みの小さい辺から順に選ぶクラスカル法や、1つの頂点から木を広げていくプリム法で求め、通信網や配線の費用を最小にする設計に応用される。

中心から放射状に伸ばした複数の軸に各項目の値をとり、点を線で結んだ多角形で表すグラフ。複数の評価項目のバランスを一目で把握でき、製品や人材の評価、他社との比較などに使う。各軸の目盛りの範囲をそろえないと、形から受ける印象が実際の差と食い違う。

辺の重みが負でないグラフで、出発点から各頂点への最短経路を求めるアルゴリズム。最短距離が確定していない頂点のうち、出発点からの距離が最小のものを確定させ、そこから出る辺で隣の頂点の距離を更新することを繰り返す。優先度付きキューを使うとO((V＋E) log V)で計算できるが、負の重みの辺があると正しく求められない。

出発点から各頂点への最短経路を、すべての辺について距離の更新（緩和）を頂点数－1回繰り返して求めるアルゴリズム。負の重みの辺があっても正しく求められ、もう1回更新して距離が変わるなら、たどるほど距離が減り続ける負の閉路があると判定できる。計算量はO(VE)で、ダイクストラ法より遅い。

グラフのすべての頂点の組の間の最短経路を一度に求める動的計画法のアルゴリズム。頂点kを経由した方が近くなるなら距離を更新するという処理を、すべての頂点kについて順に行う。計算量はO(V³)で、負の重みの辺があっても負の閉路がなければ求められ、実装が簡単で、頂点数が少ないグラフに向く。

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

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