krukshal的算法或Prims算法哪個更適合尋找最小生成樹？

可能重複：
Kruskal vs Prim krukshal的算法或Prims算法哪個更適合尋找最小生成樹？

krukshal的算法或普里姆算法哪一個是在尋找最小生成樹更好？

2010-11-22 Eric

@Adnan：你怎麼知道這是作業？ – 2010-11-22 03:51:14

http://stackoverflow.com/questions/1195872/kruskal-vs-prim – Eric 2010-11-22 03:51:58

聽起來很熟悉我幾年前算法分析類的問題 – Adnan 2010-11-22 03:52:15

我會添加一點贊成Prim算法，我沒有見過提及。如果給定N點和x和y之間距離的距離函數d（x，y），那麼使用空間O（N）（但是時間N^2）很容易實現Prim算法。

從任意點A開始，創建一個N-1大小的數組，給出從A到所有其他點的距離。選擇與最短距離相關的點B，將生成樹中的A和B鏈接起來，然後更新數組中的距離作爲已記錄到該另一個點的距離的最小值以及距其他點的距離點，注意最短的鏈接來自B和A從哪裏繼續。

我不知道類似的方法來處理由距離函數指定的稠密圖形的Kruskal算法，對於大N，在耗盡時間之前您可能用盡空間O（N^2） O（N^2）。

2010-11-22 05:23:34 mcdowella

回答