クラスカル法

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

概要

このアルゴリズムは、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) である。これらは次の理由で等価である。

E は最大でも V² であり、log V² = 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)) の計算量になる。ここでαはアッカーマン関数の逆関数で極めてゆっくり増加する。

例

	元のグラフ。辺のそばにある数値は重みである。今のところ、どの辺も強調されていない。
	AD と CE が最短（重みが5）の辺なので、まず AD を無作為に選んで強調表示している。つまり、AD を木とした。
	CE が最短の辺で、それによって閉路は形成されない（同じ木を連結する辺ではない）ので、新たに木に含める。
	次に短い DF を選び、同様に処理する。
	次に短いのは長さ 7 の AB と BE なので、無作為に AB を選ぶ。なお、B と D が同じ木に属すようになったため、BD を赤で示している。つまり BD は捨てるべき辺である。
	次に同じ長さ 7 の辺 BE を選ぶ。ここでさらに多くの辺が赤になっている。BC、DE、EF は同じ木に属する頂点を結ぶ辺であるため、捨てられる。
	最後に長さ 9 の辺 EG を選び、これで最小全域木が完成する。

正しさの証明

このアルゴリズムの正しさの証明は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: 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.

外部リンク