クラスカル法とプリム法のアルゴリズム
1. 概要
グラフ理論では、最小スパニングツリー（MST）を計算するための2つの主要なアルゴリズムがあります。
このチュートリアルでは、両方について説明し、それらの違いを見ていきます。
2. 最小スパニングツリー
スパニングツリーは、ツリーを形成し、グラフ内のすべてのノードを接続するエッジのセットです。 最小スパニングツリーは、コスト（エッジの重みの合計）が最も低いスパニングツリーです。
また、ツリーであるため、MSTは無向接続グラフについて話すときに使用される用語であることに注意してください。
例を考えてみましょう：
ご覧のとおり、赤いエッジが最小スパニングツリーを形成しています。 MSTの総コストは、取得したエッジの重みの合計です。 与えられた例では、提示されたMSTのコストは2 + 5 + 3 + 2 + 3 + 3=18です。
ただし、形成できるMSTはこれだけではありません。 たとえば、との間のエッジを取る代わりに、との間のエッジを取ることができ、コストは同じままになります。 このことから、異なるMSTが、同じ重みで異なるエッジを交換する理由であることがわかります。
したがって、アルゴリズムが同じコストでエッジを検査する順序が異なると、MSTが異なります。 ただし、もちろん、これらのMSTはすべて同じコストになるはずです。
3. クラスカルのアルゴリズム
3.1. 本旨
クラスカルアルゴリズムの背後にある主なアイデアは、重みに基づいてエッジを並べ替えることです。 その後、軽量化に基づいて1つずつエッジを取り始めます。
問題は、サイクルを十分に速く検出することです。 これを行うために、互いに素なセットのデータ構造を使用できます。 素集合データ構造により、2つのノードを1つのコンポーネントに簡単にマージできます。 また、2つのノードが以前にマージされたかどうかをすばやく確認できます。
したがって、エッジを追加する前に、まずエッジの両端が以前にマージされているかどうかを確認します。 その場合、MSTにエッジを含めません。 それ以外の場合は、MSTにエッジを追加し、互いに素なセットのデータ構造内で両方のノードをマージします。
3.2. アルゴリズム
このアルゴリズムでは、セクション3.1で説明した互いに素な集合データ構造であるという名前のデータ構造を使用します。 クラスカルのアルゴリズムの擬似コードを見てください。
まず、エッジのリストを重みに基づいて昇順で並べ替えます。 次に、すべてのエッジを反復処理します。 エッジごとに、その端が以前にマージされたかどうかを確認します。 もしそうなら、私たちはこのエッジを無視します。
それ以外の場合は、MSTの総コストを増やし、このエッジを結果のMSTに追加します。 また、このエッジの両端を互いに素なセットのデータ構造内にマージします。
最後に、計算されたMSTと取得されたエッジの合計コストを返すだけです。
クラスカルアルゴリズムの複雑さはです。ここで、はエッジの数であり、はグラフ内の頂点の数です。 この複雑さの理由は、ソートコストによるものです。
3.3. 分析
複雑さがであるため、 Kruskalアルゴリズムは、エッジがあまりないスパースグラフでより適切に使用されます。
ただし、すべてのエッジを重みに基づいて昇順で並べ替えて1つずつ調べているため、結果のMSTを細かく制御できます。 異なるMSTは同じコストで異なるエッジから発生するため、クラスカルアルゴリズムでは、これらのエッジはすべて、並べ替え時に次々に配置されます。
したがって、2つ以上のエッジの重みが同じである場合、それらの順序付けは完全に自由です。 使用する順序は、結果のMSTに影響します。 もちろん、同じ重みのエッジの順序に関係なく、コストは常に同じになります。 ただし、追加するエッジは異なる場合があります。
考慮すべきもう1つの側面は、クラスカルアルゴリズムの実装がかなり簡単であるということです。 唯一の制限は、優れた素集合データ構造と優れたソート機能を持つことです。
4. プリムのアルゴリズム
4.1. 本旨
基本的に、プリムのアルゴリズムは、ダイクストラのアルゴリズムの修正バージョンです。 まず、開始するノードを選択し、そのすべてのネイバーを優先キューに追加します。
その後、複数のステップを実行します。 各ステップで、重みが最も低いエッジを使用して到達できたノードを抽出します。 したがって、優先キューには、ノードと、このノードに到達するためのエッジの重みが含まれている必要があります。 また、渡された重みに基づいて、その中のノードをソートする必要があります。
抽出されたノードごとに、結果のMSTに追加し、MSTの合計コストを更新します。 また、すべてのネイバーもキューに追加します。
より複雑にするために、各ノードがキュー内に1回だけ表示されるようにすることができます。 たとえば、このノードに到達した重みとエッジを持つノードを取得する関数を使用できます。
ノードがすでにキュー内にあり、新しい重みが保存されている重みよりも優れている場合、関数は古いノードを削除し、代わりに新しいノードを追加します。 それ以外の場合、ノードがキュー内にない場合は、指定された重みとともにノードを追加するだけです。
4.2. アルゴリズム
プリムのアルゴリズムの次の擬似コードを検討してください。
最初に、重みがゼロでエッジのないソースノードをキューに追加します。 記号を使用して、ここに空の値を格納することを示します。 また、合計コストをゼロで初期化し、すべてのノードをMSTにまだ含まれていないものとしてマークします。
その後、複数のステップを実行します。 各ステップで、重みが最も小さいノードをキューから抽出します。 抽出されたノードごとに、抽出されたエッジの重みだけMSTのコストが増加します。 また、抽出されたノードのエッジが存在する場合は、結果のMSTに追加します。
抽出されたノードの処理が終了したら、その隣接ノードを繰り返し処理します。 結果のMSTにネイバーがまだ含まれていない場合は、この関数を使用してこのネイバーをキューに追加します。 また、エッジとエッジ自体の重みを追加します。
プリムのアルゴリズムの複雑さはです。ここで、はエッジの数であり、はグラフ内の頂点の数です。
4.3. 分析
プリムのアルゴリズムの利点は、クラスカルのアルゴリズムよりも優れている複雑さです。 したがって、 Primのアルゴリズムは、エッジが多い密集したグラフを処理する場合に役立ちます。
ただし、 Primのアルゴリズムでは、同じ重みを持つ複数のエッジが発生した場合に、選択したエッジをあまり制御できません。 その理由は、クラスカルのアルゴリズムのようにすべてのエッジではなく、これまでに検出されたエッジのみがキュー内に格納されるためです。
また、クラスカルのアルゴリズムとは異なり、プリムのアルゴリズムは実装が少し難しい。
5. 比較
2つのアルゴリズムの主な違いをいくつか強調しましょう。
ご覧のとおり、 Kruskalアルゴリズムは、実装が簡単で、結果のMSTを最適に制御するために使用する方が適切です。 ただし、Primのアルゴリズムはより複雑なを提供します。
6. 結論
このチュートリアルでは、グラフの最小全域木を計算するための主な2つのアルゴリズムについて説明しました。 まず、MSTという用語について説明しました。 次に、クラスカル法とプリム法のアルゴリズムを提示し、それぞれの分析を提供しました。
第三に、両方のアルゴリズム間の比較を提供することによって要約しました。
