クラスカル法：最小全域木のための貪欲法

手順

アルゴリズムは次のように進む。

1. すべての辺を集め、重みの非減少順にソートする。
2. 空の森から始める。この時点では、各頂点はそれぞれ独立した連結成分である。
3. ソート順に辺を調べる。ある辺が異なる二つの連結成分を結ぶ場合は追加し、そうでない場合は閉路を作るため追加しない。
4. すべての頂点を覆う一つの木ができるまで続ける。あるいは、すべての辺を調べ終えた時点で、最小全域森が得られる。

この単純な反復処理は通常、二つの頂点が同じ連結成分に属するかを判定し、選択した辺に応じて成分を併合するために、互いに素な集合（union-find）データ構造と組み合わせて実装される。

データ構造と計算量

支配的なコストは辺のソートである。辺数をE、頂点数をVとすると、ソートにはO(E log E)時間を要する。E ≤ V2であるため、これはしばしばO(E log V)とも表される。経路圧縮とランクによる併合を用いれば、union-findの操作（findとunion）は償却的にほぼ定数時間で実行できる。したがって、典型的な解析における全体の実行時間はおおむねO(E log E)である。

正しさと性質

正しさは、カット性質や閉路性質など、MSTに関する標準的な原理によって示される。すなわち、任意のカットを横切る最小重みの辺はあるMSTに含まれ、任意の閉路における最大重みの辺は、すべてのMSTで必須となることはない。クラスカル法は、利用可能で安全な辺のうち最小のものを貪欲に選ぶため、これらの性質に従ってMSTを得る。辺の重みがすべて異なる場合、MSTは一意である。等しい重みがある場合は、複数のMSTが存在しうる。

変種、実装上の注意点、用途

• 重みが限られた範囲の整数である場合には、効率的なソートやバケット法、基数法を利用できる。
• 大規模なグラフでの性能には、経路圧縮およびランクまたはサイズによる併合といったunion-findの最適化が重要である。
• 入力がすでに辺リストである場合やグラフが疎である場合、クラスカル法は特に扱いやすい。適切な優先度付きキューを用いるなら、密なグラフではプリム法のほうが適することがある。

用途には、ネットワーク設計（通信、道路、公共設備のネットワーク）、クラスタリング（単連結階層的クラスタリング）、および一部の画像分割手法が含まれる。背景知識や形式的な証明については、貪欲アルゴリズム、最小全域木、グラフモデルに関する標準的なアルゴリズムの文献や入門資料を参照するとよい。

歴史。この手法はジョセフ・B・クラスカルによって1956年に記述された。今日でも、アルゴリズムの講義で学ばれ、実務でも用いられる基本的なアルゴリズムの一つである。