[グラフ] クラスカル法

クラスカル法は、素集合データ構造を使い最小全域木の問題を解くアルゴリズムです。

全域木

ある無向グラフを考えた時、このグラフの全域木とは、グラフの頂点全てを使い構成される部分グラフで、木構造になるものです。

全域木（ぜんいきぎ、英: Spanning tree）、極大木（きょくだいき）、スパニング木、スパニングツリーとは、グラフ理論において、以下のように定義される木のことである。
グラフG(V,E) において T ⊆ E となる辺集合 T があるとき、グラフ S(V,T) が木（閉路を持たないグラフ）であるなら、 S(V,T) のことをグラフ G(V,E) の全域木であるとする。
つまり、あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のことである。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

一つのグラフの中には複数の全域木がある可能性があります。

全域木

例えば上のグラフで、緑色の線が全域木を構成していますが、(D, F) の辺は使わずに (E, F) や (F, G) の辺を使うことでも全域木を作ることができます。

最小全域木問題

最小全域木問題とは、全域木で辺に重みがある場合、複数の全域木の中で重みの総和が最小になる全域木を探す問題です。

上と同じグラフですが、緑色の線は最小全域木となっています。

もし辺を入れ替えて別の全域木を構成すると、重みの総和が大きくなってしまいます。

最小全域木

最小全域木の問題は、辺の重みが均一であれば幅優先探索、辺の重みが均一でない場合は貪欲法であるクラスカル法やプリム法で解くことができます。

クラスカル法

クラスカル法（英: Kruskal’s algorithm）は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

クラスカル法では、まず辺を重みによりソートします。例えばクイックソートを使えば、\( O (E \log E) \)で行えます。重みが最小の辺を取り出せばよいので、ヒープを使った重みによる優先度付きキューでも同様の計算量で必要な処理を行えます。

次に、一番小さい重みの辺から全域木に加えていきますが、もし閉路ができてしまうと全域木ではなくなってしまいます。ここで素集合データ構造を使うことで、閉路になるかどうかの検討が効率的に行えます。一回で1辺、つまり2頂点ずつどの木に属しているかを確認し、異なる木に属している場合は統合を行いますが、これらの操作は素集合データ構造で\( O ( \alpha (V) )\)で行えます。これを全ての辺で検討するので\( O ( \alpha (V) \times \log V ) \)で行えます。

よって、クラスカル法の計算量は \( O (E \log E) \) になります。

計算量のちゃんとした説明は以下がわかりやすいです。

Complexity

クラスカル法の正しさの証明は以下。

正しさの証明

クラスカル法の疑似コード

素集合データ構造を使ったクラスカル法の疑似コードは以下のようになります。

algorithm Kruskal(G) is
    A := ∅
    for each v ∈ G.V do
        MAKE-SET(v)
    for each (u, v) in G.E ordered by weight(u, v), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
           A := A ∪ {(u, v)}
           UNION(FIND-SET(u), FIND-SET(v))
    return A

下のグラフで具体的に考えます。

辺は重みでソートし、また頂点を素集合データ構造で保持します。