Data-structures-algorithms-prims-spanning-tree-algorithm
プリムのスパニングツリーアルゴリズム
（Kruskalのアルゴリズムとして）最小コストスパニングツリーを見つけるためのPrimのアルゴリズムは、貪欲なアプローチを使用します。 プリムのアルゴリズムは、*最短パス優先*アルゴリズムと類似しています。
Primのアルゴリズムは、Kruskalのアルゴリズムとは対照的に、ノードを単一のツリーとして扱い、指定されたグラフからスパニングツリーに新しいノードを追加し続けます。
クラスカルのアルゴリズムと対比し、プリムのアルゴリズムをよりよく理解するために、同じ例を使用します-
手順1-すべてのループと平行エッジを削除する
指定されたグラフからすべてのループと平行エッジを削除します。 平行なエッジの場合、関連するコストが最も少ないエッジを保持し、他のすべてを削除します。
ステップ2-任意のノードをルートノードとして選択する
この場合、Primのスパニングツリーのルートノードとして S ノードを選択します。 このノードは任意に選択されるため、任意のノードをルートノードにすることができます。 なぜビデオがルートノードになり得るのか疑問に思うかもしれません。 したがって、答えは、スパニングツリーにはグラフのすべてのノードが含まれており、グラフは接続されているため、ツリーの残りの部分に結合する少なくとも1つのエッジが必要です。
手順3-発信エッジを確認し、コストの低い方を選択します
ルートノード S を選択すると、S、AとS、Cがそれぞれ重み7と8の2つのエッジであることがわかります。 エッジS、Aは他のエッジよりも小さいため、選択します。
これで、ツリーS-7-Aは1つのノードとして扱われ、そこから出るすべてのエッジをチェックします。 最もコストの低いものを選択し、それをツリーに含めます。
このステップの後、S-7-A-3-Cツリーが形成されます。 ここで再びノードとして扱い、すべてのエッジを再度チェックします。 ただし、最小コストのエッジのみを選択します。 この場合、C-3-Dは新しいエッジであり、他のエッジのコスト8、6、4などよりも小さくなります。
ノード D をスパニングツリーに追加すると、2つのエッジが出て同じコストになります。 D-2-TおよびD-2-B。 したがって、どちらかを追加できます。 ただし、次のステップでは、エッジ2が最小コストとして再び生成されます。 したがって、両方のエッジを含むスパニングツリーを示しています。
2つの異なるアルゴリズムを使用した同じグラフの出力スパニングツリーが同じであることがわかります。
