クラスカルの木定理とは？わかりやすく解説

クラスカル法（英: 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$

Optimization computes maxima and minima.

カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）

一般	バリア関数ペナルティ関数法（英語版）
微分可能	ラグランジュの未定乗数法逐次二次計画法連続線形計画（英語版）

クラスカルの木定理とは？ わかりやすく解説

クラスカル法

概要

アルゴリズムの解説

性能

例

正しさの証明

全域木

急上昇のことば

「クラスカルの木定理」の関連用語

クラスカルの木定理とは？わかりやすく解説