algorithm - クラスカルのアルゴリズムとプリムのアルゴリズムをいつ使用するか

Question

重複の可能性:
Kruskal vs Prim

Prim のアルゴリズムよりも Kruskal のアルゴリズムを使用して、最小スパニング ツリーを見つけるのはいつですか? 種類ごとに、どのような種類の入力グラフとノードが適していますか? スペースと時間に関して、それらのいずれかを使用する方が効率的なのはどのような場合ですか?

あるものを他のものよりもはるかに優れたものにする彼らの特定のインプットはありますか?

Answer 1

1 つの重要な違い: グラフが切断されている場合、Prim は役に立ちません (グラフを接続する必要があります)。一方、クラスカルのものは、接続されたグラフまたは切断されたグラフで機能します。後者の場合、各接続コンポーネントの MST である最小スパニング フォレストが検出されます。