クラスカル法

クラスカル法（）は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。
概要.
このアルゴリズムは、1956年にが "Proceedings of the American Mathematical Society" で発表した (pp. 48–50)。
クラスカル法は貪欲法の一種で、最小全域木を求める他のアルゴリズムとしては、プリム法、、ブルーフカ法などがある。最小全域木とは、グラフの全ての頂点を含む木で、辺の重みの総和が最小のものを言う。連結されていないグラフでは、「最小全域森」（それぞれの連結部分の最小全域木の集合）を求められる。
アルゴリズムの解説.
クラスカル法の手順は次の通り。
 グラフの各頂点がそれぞれの木に属するように、森（木の集合） "F" を生成する（つまり頂点1個だけからなる木が頂点の個数だけ存在する）
 "S" ← グラフの全ての辺を含む集合
 while ("S" が空集合ではない)
 "S" から重みが最小の辺 "e" を削除する
 if ("e" が2つの木を連結するもの)
 "e" を森に加え、2つの木を1つにまとめる
このアルゴリズムが終了した時点で、森は単一の木となっており、元のグラフの最小全域木になっている。
性能.
グラフ内の辺数を "E"、頂点数を "V" とすると、クラスカル法の計算量はデータ構造が単純であれば "O"("E" log "E") または "O"("E" log "V") である。これらは次の理由で等価である。
この計算量は以下のように求められる。まず、辺を重みでソートするのに比較ソートを用いると "O"("E" log "E") となる。これにより、「"S" から重みが最小の辺を削除する」操作を定数時間で行えるようになる。次にどの頂点がどの木に属しているかを保持するのに素集合データ構造を使う。各辺について、2回の探索操作と1回の和集合操作が必要であり、O("E") 回となる。単純な素集合データ構造であっても "O"("E" log "V") の時間内に O("E") 回の操作を実行できる。したがって、総計算量は "O"("E" log "E") = "O"("E" log "V") である。
辺が事前にソート済みか（分布数えソートや基数ソートを使って）線形時間でソートできる場合、より洗練された素集合データ構造を使うことができ、"O"("E" α("V")) の計算量になる。ここでαはアッカーマン関数の逆関数で極めてゆっくり増加する。
正しさの証明.
このアルゴリズムの正しさの証明は2つの部分に分けられる。第一は全域木を生成していること、第二はそれが最小の重みであることである。
全域木.
重み付き連結グラフ formula_1 があり、クラスカル法で生成した formula_1 の部分グラフを formula_3 とする。常に異なる2つの木を連結する辺を加えているので、formula_3 には閉路がない。また、formula_3 の2つの部分を連結する辺を全て選んでいるので、全頂点は連結されている。したがって formula_3 は formula_1 の全域木である。
最小性.
この証明には背理法を用いる。formula_3 が最小全域木でないとすると、別に最小全域木が一つ以上存在する。それらの中から、formula_3 と共通する辺の数が最も多い木 formula_10 を選ぶ。formula_3 に含まれ formula_10 には含まれない辺の中で、本アルゴリズムによって formula_3 に最初に追加される 辺 formula_14 について考える。
formula_15 には閉路が存在する。formula_3 は木であるので、閉路を形成する辺を全部含むことはない。したがって、この閉路には formula_3 には含まれない辺 "f" が存在する。formula_18 も全域木であるから、その重みは formula_10 より小さいはずがなく、"e" の重みは "f" より小さいはずがない。ここで別の背理法を用いて "f" の重みが "e" より小さいはずがないことを証明する。formula_3 に追加する辺は常に重みの小さいほうから選んでいた。したがって、 仮に "f" の重みが "e" より小さいとすると、"f" は "e" より以前に検討されたはずで、 部分森 formula_21 への追加をするか調べたはずである（"e" は formula_10 に含まれない辺の中でformula_3 に最初に追加された辺であるため、formula_3 を形成する過程で "e" を追加する前の段階の formula_3 の部分森は formula_10 の部分森でもある）。しかし "f" は formula_10 で閉路を形成していないので、formula_28 においても閉路を形成しないはずであり、木に追加されていたはずである。これは、 "f" が formula_3 に含まれない辺であるということに反する。よって、"f" の重みは "e" より小さいことはない。
以上により、 "e" と "f" は同じ重みであることが示される。したがって formula_30 も最小全域木である。しかし formula_30 は formula_10 よりも formula_3 と共通する辺が1つ多い。これは formula_10 の定義と矛盾する。（証明終）
擬似コード.
 1 function Kruskal("G")
 2 for each vertex "v" in "G" do
 3 Define an elementary cluster "C"("v") ← {"v"}.
 4 Initialize a priority queue "Q" to contain all edges in "G", using the weights as keys.
 5 Define a tree "T" ← Ø //"T" は最終的に最小全域木の辺を含む。
 6 // n は全頂点数
 7 while "T" has fewer than "n"-1 edges do
 8 // 辺 u,v は v にとって重みが最小の経路である。
 9 ("u","v") ← "Q".removeMin()
 10 // T に閉路が含まれないようにする。T に既に u と v を結ぶ経路がない場合のみ u,v を追加する。
 11 // つまり、u と v が違うクラスター（木）に属する場合のみ u,v を追加する。
 13 Let "C"("v") be the cluster containing "v", and let "C"("u") be the cluster containing "u".
 14 if "C"("v") ≠ "C"("u") then
 15 Add edge ("v","u") to "T".
 16 Merge "C"("v") and "C"("u") into one cluster, that is, union "C"("v") and "C"("u").
 17 return tree "T"