クラスカルのアルゴリズム

クラスカルのアルゴリズム

ユークリッド距離に基づく重みを持つ完全グラフ上のクラスカルのアルゴリズムのアニメーション
クラス	最小全域木アルゴリズム
データ構造	グラフ
最悪の場合の パフォーマンス	${\displaystyle O(|E|\log |V|)}$

クラスカルのアルゴリズム^[1]は、無向の辺重み付きグラフの最小全域木を見つけます。グラフが連結されている場合、最小全域木を見つけます。これは貪欲アルゴリズムであり、各ステップで、サイクルを形成しない最小の重みの辺をフォレストに追加します。^[2]このアルゴリズムの主要なステップは、ソートと、サイクルを検出するための分離セットデータ構造の使用です。その実行時間は、すべてのグラフの辺を重みでソートする時間によって大きく左右されます。

連結された重み付きグラフの最小全域木は、サイクルのない連結された部分グラフであり、部分グラフ内のすべての辺の重みの合計が最小になります。連結されていないグラフの場合、最小全域木は連結された各コンポーネントの最小全域木で構成されます。

このアルゴリズムは1956年にジョセフ・クラスカルによって初めて発表され^[3]、その後すぐにローバーマンとワインバーガー（1957）によって再発見されました^{[4] 。この問題に対する他のアルゴリズムには、}プリムのアルゴリズム、ボルフカのアルゴリズム、逆削除アルゴリズムなどがあります。

アルゴリズムは次の手順を実行します。

• 入力グラフ内の各頂点に対して、最初は個別の単一頂点ツリーで構成されるフォレスト (ツリーのセット) を作成します。
• グラフのエッジを重みで並べ替えます。
• グラフのエッジを重みの昇順でループします。各エッジについて:
  • 現在のフォレストにエッジを追加するとサイクルが作成されるかどうかをテストします。
  • そうでない場合は、フォレストにエッジを追加して、2 つのツリーを 1 つのツリーに結合します。

アルゴリズムの終了時に、フォレストはグラフの最小全域フォレストを形成します。グラフが連結されている場合、フォレストは単一のコンポーネントを持ち、最小全域木を形成します。

次のコードは、分離集合データ構造を使用して実装されています。フォレストF を無向エッジの集合として表し、分離集合データ構造を使用して、2 つの頂点が同じツリーの一部であるかどうかを効率的に判断します。

アルゴリズムKruskal( G )は
    F:= ∅
    GVの各vに対して
        メイクセット(v)
    GE内の各{u, v}について、重み({u, v})で順序付けし、FIND
         -SET(u) ≠ FIND-SET(v)の場合、
            F := F ∪ { {u, v} }
            UNION(FIND-SET(u), FIND-SET(v))
    Fを
返す

E個の辺とV個の頂点を持つグラフの場合、クラスカルのアルゴリズムは、単純なデータ構造を使用して、O ( E log E )時間で実行できることが示されます。ここで、 O は時間を大きな O 表記で表し、log は任意の底に対する対数です( O表記内では、すべての底に対する対数は等価です。定数倍を除いて同じだからです)。この時間制限は、代わりにO ( E log V )と記述されることが多く、孤立した頂点のないグラフでは等価です。これらのグラフでは、V /2 ≤ E < V ²であり、 VとEの対数は、やはり互いに定数倍以内だからです。

この制限を達成するには、まず比較ソートを使用してエッジを重みでO ( E log E )時間でソートします。ソートが完了すると、エッジごとに定数時間でソートされた順序でエッジをループ処理できるようになります。次に、各コンポーネントの頂点セットを持つ分離セットデータ構造を使用して、どの頂点がどのコンポーネントにあるかを追跡します。頂点ごとに別々のセットを持つこの構造を作成するには、V 回の演算とO ( V )時間かかります。すべてのエッジの最後の反復処理では、エッジごとに 2 つの検索演算と、場合によっては 1 つの結合演算が実行されます。これらの演算には、1 回の償却時間 O ( α ( V ))時間かかり、最悪の場合、このループの合計時間はO ( E α ( V ))になります。ここで、 α は極めてゆっくりと増加する逆アッカーマン関数です。時間制限のこの部分はソート手順の時間よりもはるかに短いため、アルゴリズムの合計時間はソート手順の時間に簡略化できます。

エッジがすでにソートされている場合、またはエッジの整数重みが十分に小さいため、カウンティングソートや基数ソートなどの整数ソートアルゴリズムを使用して線形時間でソートできる場合、分離セット演算はアルゴリズムの残りの部分の中で最も遅く、合計時間はO ( E α( V ))です。

証明は 2 つの部分から成ります。まず、アルゴリズムが全域木を生成することが証明されます。次に、構築された全域木の重量が最小であることが証明されます。

が連結された重み付きグラフであり、がアルゴリズムによって生成された のサブグラフであるとします。はサイクルを持つことができません。定義により、サイクルになるエッジは追加されないためです。 の 2 つのコンポーネントを結合する最初のエッジがアルゴリズムによって追加されるため、 は切断されません。したがって、は の全域木です。 ${\displaystyle G}$${\displaystyle Y}$${\displaystyle G}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle G}$

次の命題Pが真であることを帰納法によって示します。アルゴリズムの任意の段階で選択されたエッジの集合がFである場合、 F を含み、アルゴリズムによって拒否されたエッジをまったく含まない最小全域木が存在します。

• 明らかに、 Fが空のときは、最初はPが真です。つまり、任意の最小全域木で十分であり、重み付き接続グラフには常に最小全域木があるため、最小全域木が存在します。
• ここで、 P が何らかの非最終エッジ セットFに対して真であると仮定し、T をF を含む最小全域木とします。
  • 次に選択されるエッジeもT内にある場合、F + eに対してP は真です。
  • それ以外の場合、e がTにない場合、 T + eにはサイクルCがあります。サイクルCには、 F + eに属さないエッジが含まれます 。これは、 eをFに追加するとサイクルを形成しないが、 T ではサイクルを形成するためです。f を、 Cに含まれるがF + eには含まれないエッジとします。 f はT + eに属しますが、 F + eには属さないため、 fもTに属することに注意してください。 Pにより 、f はアルゴリズムによって考慮されていません。したがって、 f は少なくともeと同じ重みを持つ必要があります。 すると、T − f + e は木になり、Tと同じかそれ以下の重みを持ちます。 ただし、T は最小全域木なので、T − f + e はTと同じ重みを持ちます。そうでなければ矛盾が生じ、T は最小全域木ではなくなります。 したがって、T − f + eはF + e を含む最小全域木であり、ここでもP が成り立ちます。
• したがって、帰納法の原理により、F が全域木になったときにPが成立しますが、これはF自体が最小全域木である場合にのみ可能です。

クラスカルのアルゴリズムは本質的に逐次的であり、並列化は困難です。しかし、エッジの初期ソートを並列に実行したり、バイナリヒープの並列実装を使用して各反復で最小重みのエッジを抽出することは可能です。^[5] 並列ソートはプロセッサ上で時間内に実行できるため、 ^[6]クラスカルのアルゴリズムの実行時間はO ( E α( V )) に短縮できます。ここで、α は単一値アッカーマン関数の逆です。 ${\displaystyle O(n)}$${\displaystyle O(\log n)}$

^{Kruskal アルゴリズムの変形である Filter-Kruskal は、Osipov ら[7]}によって説明されており、並列化に適しています。Filter-Kruskal の基本的な考え方は、クイックソートと同様の方法でエッジを分割し、同じツリーの頂点を接続するエッジを除外してソートのコストを削減することです。次の疑似コードはこれを示しています。

関数filter_kruskal(G)は、
     |GE| < kruskal_threshold
        の場合、 kruskal(G)を返します。
    ピボット = choose_random(GE)
    E ≤ , E > = パーティション(GE, ピボット)
    A = フィルタークラスカル(E ≤ )
    E > = フィルター(E > )
    A = A ∪ filter_kruskal(E > )
     Aを返す

関数partition(E, pivot)は、 
    E ≤ = ∅、E > = ∅
    です。 foreach (u, v) in E で、 weight(u, v) ≤ pivotの場合、 
            E ≤ = E ≤ ∪ {(u, v)}
        を実行し、そうでない場合は、 
            E > = E > ∪ {(u, v)} を実行し、
     E ≤、E >を返します。
        

関数filter(E)は
    E f = ∅
     foreach (u, v) in E であり
        、 find_set(u) ≠ find_set(v)の場合、 
            E f = E f ∪ {(u, v)}
    を返す。

フィルタ・クラスカル法は、プロセッサ間でエッジを分散させることでソート、フィルタリング、パーティショニングを簡単に並列に実行できるため、並列化に適しています。^[7]

最後に、クラスカルのアルゴリズムの並列実装の他のバリエーションが検討されました。例としては、ヘルパースレッドを使用してバックグラウンドで MST の一部ではないエッジを削除するスキーム^[8]や、 p 個のサブグラフに対して順次アルゴリズムを実行し、それらのサブグラフをマージして最終的な MST が 1 つだけ残るようにするバリエーションなどがあります。^[9]

• プリムのアルゴリズム
• ダイクストラのアルゴリズム
• ボルフカのアルゴリズム
• 逆削除アルゴリズム
• 単一リンククラスタリング
• 貪欲な幾何学的スパナ

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 、Clifford Stein。アルゴリズム入門、第 2 版。MIT Press および McGraw-Hill、2001 年。ISBN 0-262-03293-7。セクション23.2 : KruskalとPrim のアルゴリズム、pp. 567–574。 
• Michael T. GoodrichおよびRoberto Tamassia。『Java のデータ構造とアルゴリズム』、第 4 版。John Wiley & Sons, Inc.、2006 年。ISBN 0-471-73884-0 。セクション 13.7.1: Kruskal のアルゴリズム、632 ページ。 

• 記事の例のデータ。
• 最小全域木を計算するための Gephi プラグインのソース コード。
• クラスカルのアルゴリズムと C++ での例とプログラム
• 乱数に適用した C++ の Kruskal アルゴリズム コード
• Python でのクラスカルのアルゴリズムのコードと説明