Motivation

Kruskal法がすべての辺をグローバルにソートしてUnion-Findを使用するのに対し、Prim法は単一の成長する木を保持し、繰り返し最も近い外部の頂点に手を伸ばします。

なぜPrim法を学ぶのか？

• 密なグラフ: 適切な構造を用いたPrim法は、辺が多い場合に効率的です。
• カットプロパティ: 現在の木から離れる最も安価な辺を追加することが常に安全である理由を、実践的に説明するものです。
• 1つの問題に対する2つの視点: Prim法とKruskal法を比較することで、最小全域木への理解が深まります。

グラフのすべてのMST（最小全域木）は同じ辺の重みを共有するため、Prim法とKruskal法は常に同じ合計重みを報告します。