クラスカル法のソースを表示

'''クラスカル法'''（{{lang-en-short|Kruskal's algorithm}}）は、[[グラフ理論]]において重み付き[[連結グラフ]]の最小[[全域木]]を求める[[最適化問題]]の[[アルゴリズム]]である。

== 概要 ==
このアルゴリズムは、[[1956年]]に{{仮リンク|ジョゼフ・クラスカル|en|Joseph Kruskal}}が ''Proceedings of the American Mathematical Society'' で発表した (pp. 48&ndash;50)。

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

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

 グラフの各頂点がそれぞれの[[木 (数学)|木]]に属するように、森（木の集合） ''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''<sup>2</sup> であり、log ''V''<sup>2</sup> = 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'')) の計算量になる。ここでαは[[アッカーマン関数]]の逆関数で極めてゆっくり増加する。

== 例 ==

{| border=1 cellspacing=0 cellpadding=5
|[[画像:Prim_Algorithm_0.svg|200px]]
|元のグラフ。辺のそばにある数値は重みである。今のところ、どの辺も強調されていない。
|-
|[[画像:Kruskal Algorithm 1.svg|200px]]
|'''AD''' と '''CE''' が最短（重みが5）の辺なので、まず '''AD''' を無作為に選んで強調表示している。つまり、'''AD''' を木とした。
|-
|[[画像:Kruskal Algorithm 2.svg|200px]]
|'''CE''' が最短の辺で、それによって[[閉路]]は形成されない（同じ木を連結する辺ではない）ので、新たに木に含める。
|-
|[[画像:Kruskal Algorithm 3.svg|200px]]
|次に短い '''DF''' を選び、同様に処理する。
|-
|[[画像:Kruskal Algorithm 4.svg|200px]]
|次に短いのは長さ 7 の '''AB''' と '''BE''' なので、無作為に '''AB''' を選ぶ。なお、'''B''' と '''D''' が同じ木に属すようになったため、'''BD''' を赤で示している。つまり '''BD''' は捨てるべき辺である。
|-
|[[画像:Kruskal Algorithm 5.svg|200px]]
|次に同じ長さ 7 の辺 '''BE''' を選ぶ。ここでさらに多くの辺が赤になっている。'''BC'''、'''DE'''、'''EF''' は同じ木に属する頂点を結ぶ辺であるため、捨てられる。
|-
|[[画像:Kruskal Algorithm 6.svg|200px]]
|最後に長さ 9 の辺 '''EG''' を選び、これで最小全域木が完成する。
|}

== 正しさの証明 ==
このアルゴリズムの正しさの証明は2つの部分に分けられる。第一は全域木を生成していること、第二はそれが最小の重みであることである。

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

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

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

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

== 擬似コード ==
  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: ''[http://links.jstor.org/sici?sici=0002-9939(195602)7%3A1%3C48%3AOTSSSO%3E2.0.CO%3B2-M 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.

== 外部リンク ==
* [http://students.ceid.upatras.gr/~papagel/project/kruskal.htm クラスカル法のアニメーション（Javaアプレット）]
* [http://www.cut-the-knot.org/Curriculum/Games/Mazes.shtml クラスカル法とプリム法で迷路を生成して解く] at cut-the-knot
* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml Minimum Spanning Tree Problem: Kruskal's Algorithm]

{{最適化アルゴリズム}}
{{アルゴリズム}}

{{DEFAULTSORT:くらすかるほう}}
[[Category:グラフ理論]]
[[Category:アルゴリズム]]
[[Category:数学に関する記事]]
[[Category:組合せ最適化]]
[[Category:数学のエポニム]]