クラスカル法

クラスカル法とは

クラスカル法は、グラフ理論において、重み付き連結グラフの最小全域木を求めるためのアルゴリズムです。このアルゴリズムは、1956年にジョセフ・クラスカルによって発表され、その効率性とシンプルさから広く利用されています。

最小全域木とは

最小全域木とは、グラフの全ての頂点を含み、かつ辺の重みの総和が最小となる木のことです。グラフが連結でない場合は、各連結成分に対して最小全域木を求めることで、「最小全域森」が得られます。

アルゴリズムの概要

クラスカル法は、以下の手順で最小全域木を構築します。

1. 初期化: 各頂点がそれぞれ独立した木（森）を形成するように設定します。
2. 辺のソート: グラフ内の全ての辺を重みの小さい順にソートします。
3. 辺の選択: 重みが小さい順に辺を選択し、以下の条件を満たす場合に木に追加します。
選択した辺が、既に構築された木の中で閉路を作らない場合
選択した辺が、異なる木を連結する場合
4. 繰り返し: 全ての頂点が単一の木に連結されるまで、ステップ3を繰り返します。

アルゴリズムの計算量

グラフの辺数をE、頂点数をVとすると、クラスカル法の計算量は通常O(E log E)またはO(E log V)となります。これは、辺のソートにO(E log E)の時間がかかり、素集合データ構造を使用して各辺に対してO(log V)の操作を行うためです。

辺のソート: 辺を重みでソートするのに、比較ソートを使う場合は O(E log E) の計算量が必要です。
素集合データ構造: 各頂点がどの木に属しているかを管理するのに素集合データ構造を利用します。各辺に対して2回の探索と1回の結合が必要になり、この操作は全体で O(E) 回行われます。単純な素集合データ構造でも O(E log V) 時間で O(E) 回の操作が可能です。
線形時間ソートの場合: もし辺が事前にソートされているか、分布数えソートや基数ソートを使って線形時間でソートできる場合、より高度な素集合データ構造を使うことで、計算量をO(E α(V))に減らせます。ここで、αはアッカーマン関数の逆関数であり、非常に緩やかに増加する関数です。

正しさの証明

クラスカル法によって生成される木が、全域木であり、かつ最小の重みを持つことを証明します。

1. 全域木であること: クラスカル法では常に異なる2つの木を連結する辺を追加していくため、閉路はできません。また、グラフのすべての頂点を連結するので全域木です。
2. 最小性: 背理法を用います。クラスカル法で生成された木 Y が最小全域木でないと仮定します。この場合、Y と共通の辺が最も多い最小全域木 Y1 が存在します。ここで、Y に含まれるが Y1 に含まれない辺 e を考えます。Y1 に e を加えると閉路ができるため、その閉路には Y に含まれない辺 f が存在します。このとき、もし f の重みが e より小さいと、クラスカル法では f を先に選択するはずなので矛盾します。したがって、e と f の重みは同じであり、Y1 から f を除いて e を加えた木も最小全域木となり、Y との共通辺が増えるため、最初の Y1 の定義と矛盾します。

擬似コード

以下はクラスカル法の擬似コードです。


function Kruskal(G)
for each vertex v in G do
Define an elementary cluster C(v) ← {v}.
Initialize a priority queue Q to contain all edges in G, using the weights as keys.
Define a tree T ← Ø //T は最終的に最小全域木の辺を含む。
// n は全頂点数
while T has fewer than n-1 edges do
// 辺 u,v は v にとって重みが最小の経路である。
(u,v) ← Q.removeMin()
// T に閉路が含まれないようにする。T に既に u と v を結ぶ経路がない場合のみ u,v を追加する。
// つまり、u と v が違うクラスター（木）に属する場合のみ u,v を追加する。
Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
if C(v) ≠ C(u) then
Add edge (v,u) to T.
Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).
return tree T

他のアルゴリズムとの比較

クラスカル法は、最小全域木を求めるための他のアルゴリズム（プリム法、ブルーフカ法など）と並んで、重要なアルゴリズムの一つです。特に、辺の数が少ない疎なグラフに対して、効率的な解法として知られています。

まとめ

クラスカル法は、グラフ理論における基本的なアルゴリズムであり、ネットワーク設計や最適化問題など、様々な分野で応用されています。そのシンプルな実装と効率性から、幅広く活用される価値の高いアルゴリズムです。

関連項目

プリム法
ブルーフカ法
ダイクストラ法
ツォルンの補題

参考文献

Joseph. B. Kruskal: 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–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アプレット）
クラスカル法とプリム法で迷路を生成して解く at cut-the-knot
* Minimum Spanning Tree Problem: Kruskal's Algorithm

もう一度検索