クラスカル法

**クラスカル法**（クラスカルほう、）は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。

## 概要
このアルゴリズムは、1956年にが *Proceedings of the American Mathematical Society* で発表した (pp. 48&ndash;50)。

クラスカル法は貪欲法の一種で、最小全域木を求める他のアルゴリズムとしては、プリム法、逆削除法、ブルーフカ法などがある。最小全域木とは、グラフの全ての頂点を含む木で、辺の重みの総和が最小のものを言う。連結されていないグラフでは、「最小全域森」（それぞれの連結部分の最小全域木の集合）を求められる。

## アルゴリズムの解説
クラスカル法の手順は次の通り。

 グラフの各頂点がそれぞれの木に属するように、森（木の集合） *F* を生成する（つまり頂点1個だけからなる木が頂点の個数だけ存在する）
 *S* ← グラフの全ての辺を含む集合
 while (*S* が空集合ではない)
     *S* から重みが最小の辺 *e* を削除する
     if (*e* が2つの木を連結するもの)
         *e* を森に加え、2つの木を1つにまとめる

このアルゴリズムが終了した時点で、森は単一の木となっており、元のグラフの最小全域木になっている。

## 性能
グラフ内の辺数を *E*、頂点数を *V* とすると、クラスカル法の計算量はデータ構造が単純であれば *[[ランダウの記号|O]]*(*E* log *E*) または *O*(*E* log *V*) である。これらは次の理由で等価である。
* *E* は最大でも *V*2 であり、log *V*2 = 2 log *V* であるから log *E* は *O*(log *V*) である。
* 孤立した頂点はそれ自体が必ず最小全域木となるので無視すると、*V* ≤ *E*+1 であるから log *V* は *O*(log *E*) である。

この計算量は以下のように求められる。まず、辺を重みでソートするのに比較ソートを用いると *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つの部分に分けられる。第一は全域木を生成していること、第二はそれが最小の重みであることである。

### 全域木
重み付き連結グラフ P があり、クラスカル法で生成した P の部分グラフを Y とする。常に異なる2つの木を連結する辺を加えているので、Y には閉路がない。また、Y の2つの部分を連結する辺を全て選んでいるので、全頂点は連結されている。したがって Y は P の全域木である。

### 最小性
この証明には背理法を用いる。Y が最小全域木でないとすると、別に最小全域木が一つ以上存在する。それらの中から、Y と共通する辺の数が最も多い木 Y_1 を選ぶ。Y に含まれ Y_1 には含まれない辺の中で、本アルゴリズムによって Y に最初に追加される 辺 e について考える。

Y_1 \cup {e} には閉路が存在する。Y は木であるので、閉路を形成する辺を全部含むことはない。したがって、この閉路には Y には含まれない辺 *f* が存在する。Y_2=Y_1 \cup {e} \setminus {f} も全域木であるから、その重みは Y_1 より小さいはずがなく、*e* の重みは *f* より小さいはずがない。ここで別の背理法を用いて *f* の重みが *e* より小さいはずがないことを証明する。Y に追加する辺は常に重みの小さいほうから選んでいた。したがって、 仮に *f* の重みが *e* より小さいとすると、*f* は *e* より以前に検討されたはずで、 部分森 Y_3 \subset Y\cap Y_1 への追加をするか調べたはずである（*e* は Y_1 に含まれない辺の中でY に最初に追加された辺であるため、Y を形成する過程で *e* を追加する前の段階の Y の部分森は Y_1 の部分森でもある）。しかし *f* は Y_1 で閉路を形成していないので、Y_3 においても閉路を形成しないはずであり、木に追加されていたはずである。これは、 *f* が Y に含まれない辺であるということに反する。よって、*f* の重みは *e* より小さいことはない。

以上により、 *e* と *f* は同じ重みであることが示される。したがって Y_2 も最小全域木である。しかし Y_2 は Y_1 よりも Y と共通する辺が1つ多い。これは Y_1 の定義と矛盾する。（証明終）

## 擬似コード
  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*

## 参考文献
* Joseph. B. Kruskal: *[https://www.jstor.org/stable/2033241 On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem]*. In: *Proceedings of the American Mathematical Society*, Vol 7, No. 1 (Feb, 1956), pp. 48–50
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567&ndash;574.
* Michael T. Goodrich and Roberto Tamassia. *Data Structures and Algorithms in Java*, Fourth Edition. John Wiley & Sons, Inc., 2006. ISBN 0-471-73884-0. Section 13.7.1: Kruskal's Algorithm, pp.632.

## 関連項目
* プリム法
* ブルーフカ法
* ダイクストラ法
* ツォルンの補題

## 外部リンク
* クラスカル法のアニメーション（Javaアプレット）
* クラスカル法による最小全域木を求めるアルゴリズム