圖算法：Prim

我想知道圖G的任何最小生成樹是否可以通過在此圖上執行算法Prim來提供？圖算法：Prim

Prim算法給我們提供了所有可能的MST嗎？

我不明白。你問「如果有多於一個MST，是從'random'選擇的prim生成的MST嗎？」？ – amit

不，我知道我們可以有多個MST，但是Prim算法能否給我們提供所有可能的MST？ – streaming116

可能存在指數級的MST。想想所有權重= 1的集團。 Prim是多項式，所以答案是否定的 - 它不會給你*全部* MSTs – amit

我在想圖G中的任何最小生成樹是否可以是由在此圖上執行算法Prim提供？

Prim算法被稱爲是一個很好的算法來尋找最低生成樹。

2012-08-27 12:27:34 nurettin

你能證明它嗎？ – streaming116

我真的不認爲這是OP之後的事情。 – amit

對我來說很明顯，一個迭代地去除邊緣同時保持距離（或權重）不變的算法最終會給MST。 – nurettin

由於Prim's algorithm從一個加權的，連通的無向圖構建了一個MST，可以，您可以使用它從這樣的圖中獲取最小生成樹。如果圖形沒有連接，它將不起作用（但是因爲沒有生成樹，所以也不會有任何其他算法）。如果你的圖不是加權的，它只會創建一個生成樹a。

2012-08-27 12:28:11 Joey

我想用它來擁有所有的MST ...... – streaming116

如果您使用Prim的一次獲取MST，然後刪除邊緣。然後再次使用prim來查看是否仍然可以獲得相同長度的MST。如果你這樣做，重複，否則把邊緣放回去除另一個邊緣。它會變慢...也許只能消除重的邊緣？

2012-08-27 12:40:22

回答