プリム法とクラスカル法の違い

この投稿では、プリム法とクラスカル法のアルゴリズムの違いを理解します。

最小スパニングツリー（MST）のためのクラスカルのアルゴリズム

• 接続された無向グラフが与えられた場合、そのようなグラフのスパニングツリーは、すべての頂点を接続するツリーであるサブグラフです。
• 1つのグラフに複数のスパニングツリーを含めることができます。
• 重み付きの接続された無向グラフの最小スパニングツリー（MST）（最小重みスパニングツリーとも呼ばれます）は、他のすべてのスパニングツリーの重み以下の重みを持つスパニングツリーです。
• スパニングツリーの重みは、スパニングツリーのすべてのエッジに関連付けられた重みを加算することによって決定されます。
• 最小スパニングツリーは、グラフ内で最小の重みを持つ頂点から構築できます。
• 1つのノードが1回だけトラバースされます。
• まばらなグラフですばやく実行されます。
• 時間計算量はO（E log V）です。ここで、Vは頂点の数です。
• 切断されたコンポーネントでも機能します。

クラスカルのアルゴリズムを使用してMSTを見つける手順：

• 関連する重みの昇順でエッジを並べ替えます。
• 最小のエッジを選択します。
• その時点までに形成されたスパニングツリーとサイクルが形成されているかどうかを確認します。
• サイクルが形成されていない場合は、このエッジを含める必要があります。
• それ以外の場合は、破棄できます。
• スパニングツリーにV-1エッジが含まれるまで、ステップ2、3、4が繰り返されます。

プリムのアルゴリズム最小スパニングツリー（MST）

• これはクラスカルのアルゴリズムに似ています。つまり、欲張りアルゴリズムです。
• 空のスパニングツリーから始まります。 2セットの頂点が維持されます。
• 最初のセットには、MSTにすでに含まれている頂点が含まれますが、他のセットには、まだ含まれていない頂点が含まれます。
• すべてのステップで、アルゴリズムは2つのセットを接続するすべてのエッジを考慮します。次に、これらのエッジの中から最小の重みエッジを選択します。
• このステップの後、アルゴリズムはMSTを含むセットのエッジのもう一方のエンドポイントに移動します。
• 最小スパニングツリーは、グラフ内の任意の頂点から構築できます。
• 最小距離値を取得するために、1つのノードが複数回移動します。
• 時間計算量はO（V2）です。ここで、Vは頂点の数です。今回は、フィボナッチヒープを使用して複雑さをO（E + log V）に拡張できます。
• 密グラフですばやく実行されます。
• 接続されたコンポーネントを提供し、接続されたグラフでのみ機能します。

プリムのアルゴリズムを使用してMSTを見つける手順：

• MSTにすでに含まれている頂点を追跡するmstSetが作成されます。
• キー値は、入力グラフのすべての頂点に割り当てられます。
• キー値は最初は「INFINITE」として割り当てられます。
• 最初に選択できるように、キー値0が最初の頂点に割り当てられます。
• mstSetにすべての頂点が含まれていない場合は、以下の手順に従います。
  • mstSetに存在せず、最小のキー値を持つ頂点'u'が選択されます。
  • この「u」はmstSetに含まれるようになりました。
  • 「u」の隣接するすべての頂点のキー値が更新されます。
  • これは、隣接するすべての頂点を反復処理することで実行できます。
  • 隣接するすべての頂点'v'について、エッジ'u'-'v'の重みが前のキー値'v'の重みよりも小さい場合、キー値は'u-v'の重みとして更新されます。 '。