クラスカル法

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

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

問題を段階に分け、各段階でその時点で最も良く見える選択を繰り返して解を組み立てるアルゴリズムの設計手法。高速だが、常に全体の最適解が得られるとは限らない。ダイクストラ法や、最小全域木を求めるクラスカル法・プリム法は、貪欲法で最適解が得られる例である。

辺の重みが負でない重み付きグラフで、出発点から各頂点への最短経路を求めるアルゴリズム。最短距離が確定していない頂点のうち距離が最小のものを確定させ、そこから隣接する頂点の距離を更新することを繰り返す。OSPFの経路計算に使われている。

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