クラスカとPRM

コンピュータサイエンスにおいて、プリムとクラスカルのアルゴリズムは、接続された重み付き無向グラフの最小スパニングツリーを見つける貪欲なアルゴリズムです。スパニングツリーとは、グラフの各ノードがパスで結ばれているようなグラフの部分グラフのことで、これがツリーとなります。各スパニングツリーには重みがあり、すべてのスパニングツリーの中で可能な限り最小の重み/コストを持つものが最小スパニングツリー（MST）である。

プリムアルゴリズムの詳細

このアルゴリズムは、1930年にチェコの数学者Vojtěch Jarníkが開発し、1957年にコンピュータ科学者のRobertc.Primが独自に開発したもので、1959年にEdsger Dykstraが再発見した。このアルゴリズムは、3つの重要なステップに分けることができます。

n個のノードを持つ連結グラフと各エッジのそれぞれの重みが与えられたとき。

1 グラフから任意のノードを選択し、木 T に追加する（最初のノードとなる）。

2 木のノードに接続された各エッジの重みを考え、最小値を選ぶ。木Tのもう一方の端にエッジとノードを追加し、グラフからエッジを削除する。(極小値が2つ以上存在する場合は、いずれかを選択します）

n-1個のエッジが木に追加されるまで、ステップ2を繰り返す。

この方法では、ツリーは任意のノードから始まり、各サイクルにおいてそのノードから拡張していく。したがって、演算が**正則に行われるためには、グラフは連結グラフでなければならない。Primアルゴリズムの基本形は、時間複雑度がO(V2)である。

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

ジョセフ・クラスカルの開発したアルゴリズムは、『Journal of American Mathematical Society』の1956年発行号に掲載された。クラスカルのアルゴリズムは、3つの簡単なステップで表現することもできる。

n個のノードを持つグラフと、各エッジのそれぞれの重みが与えられたとき

1 ダイアグラム全体でウェイトが最小のアークを選択し、ツリーに追加して、ダイアグラムから削除します。

2 残りのエッジは、ループを形成しないように重みの少ないエッジを選択します。ツリーにエッジを追加し、グラフからエッジを削除します。(極小値が2つ以上ある場合は、いずれかを選択します）

手順 2 の作業を繰り返す。

この方法では、アルゴリズムが最も重みのないエッジから始まり、各サイクルごとに各エッジを選択し続ける。したがって、このアルゴリズムではグラフを連結する必要がない。クラスカルのアルゴリズムの時間計算量はO(logV)

KruskalのアルゴリズムとPrimのアルゴリズムの違いは何ですか？

-Primのアルゴリズムはノードで初期化されるが、Kruskalのアルゴリズムはエッジで初期化される。

-Primのアルゴリズムは、あるノードから別のノードへ拡張するのに対し、Kruskalのアルゴリズムは、最後のステップに基づかない方法でエッジを選択する。

-プリムアルゴリズムでは、グラフは連結グラフでなければならないが、クラスカルのアルゴリズムは、切断グラフでも動作することができる。