Prim's和Kruskal算法

Prim's和Kruskal算法都生成最小生成樹。根據切割屬性，這些算法的樹的總成本將是相同的，但是這兩種算法有可能給出不同的MST具有相同的總成本，假設我們在面對多種選擇時按字母順序選擇它。例如，我們比較max（source，dest），對於邊A-> B和B-> C，我們比較A→B和B→B-。Prim's和Kruskal算法

謝謝

來源

2012-11-09 user1687035

假設你的比較處理，其中兩邊緣成本相等，具有相同的最大值（來源，DEST）字符，它永遠不會宣佈任何兩條邊相等的情況下。如果存在多個MST的可能性，則圖中至少兩條邊必須相等。因此，MST是獨一無二的，Prim和Kruskal的算法都會返回相同的結果。另一方面，如果比較器聲明邊A-> B（成本1）和A-> C（成本1）相等，則算法可能會生成不同的MST，具體取決於哪個他們首先考慮邊緣（A-> B或A-> C）。

來源

2012-11-13 02:43:15 jma127

的確，如果存在多個MST的可能性，則圖中至少有兩條邊必須相等。但是，這並不意味着如果比較器聲明每個邊緣不同，則只有一個MST。是否有數學證明當比較器聲明每個邊緣不同時，Prim和Kruskal必然會生成相同的MST？ – user1687035

要回答上述問題：如果圖G具有不同的邊權重，則它具有唯一的MST。我認爲這意味着無論您從Prim的哪個節點開始，您都會爲Kruskal獲得同樣獨特的MST。 – pennetti

Prim's和Kruskal算法

回答

相關問題