このグラフでアルゴリズム Prim を実行することで、グラフ G の最小スパニング ツリーを提供できるかどうか疑問に思っていました。
Prim アルゴリズムは、考えられるすべての MST を提供してくれますか?
3 に答える
0
このグラフでアルゴリズム Prim を実行することで、グラフ G の最小スパニング ツリーを提供できるかどうか疑問に思っていました。
Prim のアルゴリズムは、最小全域木を見つけるための優れたアルゴリズムとして知られています。
于 2012-08-27T12:27:34.757 に答える
0
Prim のアルゴリズムは、重み付けされた接続された無向グラフから MST を構築するため、そのようなグラフから最小スパニング ツリーを取得するために使用できます。グラフが接続されていない場合、機能しません (ただし、スパニング ツリーがないため、他のアルゴリズムも機能しません)。グラフが重み付けされていない場合、スパニング ツリーが作成されます。
于 2012-08-27T12:28:11.670 に答える
0
Prim's once を使用して MST を取得する場合は、エッジを削除します。次に、もう一度プリムを使用して、同じ長さの MST を取得できるかどうかを確認します。その場合は繰り返し、そうでない場合はエッジを元に戻し、別のエッジを削除します。遅くなります...おそらく重いエッジのみを削除しますか？
于 2012-08-27T12:40:22.340 に答える