最小生成樹：Kruskal＆Prim

Question

我正在修改一個測試，並且遇到了兩個有關最小生成樹的問題，這些問題我不確定，想測試我的答案。

第一個問：如果一個圖有多個最小生成樹，Kruskal和Prim的最小生成樹算法會生成相同的樹嗎？我在想，他們不一定是因爲算法不同。克魯斯卡爾依賴於按重量排序的邊緣，而Prim沒有，所以它們可以從不同的頂點開始，從而生成不同的樹。

第二個問題問：如果一個圖有多個最小生成樹，應該如何修改Kruskal算法來生成所有這些？我認爲人們需要考慮通過頂點的循環結構，以便每次開始頂點變化，因爲邊緣值可能是相同的。因此，通過依次將每個頂點作爲起始頂點來生成樹。換句話說，按照頂點編號排序，而不是單靠邊重量。

Answer 1

如果一個圖有多個最小生成樹，Kruskal和Prim的最小生成樹算法會生成相同的樹嗎？

不，不需要Prim和Kruskals算法生成相同的MST。一個圖可以有很多MST，兩種算法都可以產生不同的結果。但是兩個MST的邊緣類型必然是相同的。即，如果您對兩個MST的邊緣進行多重集合，那麼這兩個多重集合一定是相等的。你可以找到這個證明here

如果一個圖有多個最小生成樹，應該如何修改Kruskal算法來生成所有這些？

似乎沒有直接減少kruskal的MST算法來查找圖中的所有MST。你最好的選擇將是

第1步：按kruskals的方式對圖的邊進行排序。

第2步：現在對於排序列表中的每條邊，可能會發生兩件事。邊緣位於MST中，或者不在。因此，對於排序列表中的每條邊，我們將檢查這兩種情況，並創建兩個新的Union-Find數據結構並在其他邊上遞歸。

僞代碼：

Step1: sort edges in ascending order 
Step2: now call printAllMsts(0, new UnionFind(V)) 

void printAllMsts(int edgeNum, UnionFind U){ 
    if(edgeNum == edges.length){ // If no more edges to add 
     if(U.numEdges == V-1){ // If U has V-1 edges, then we have an MST 
      printMst(); 
     } 
     return; 
    } 

    if(edges[edgeNum+1] == edges[edgeNum]){ 
     printAllMsts(edgeNum+1, U); // when E is not taken in the MST 
    } 

    edge E = edges[edgeNum]; 
    If(E can be a part of some MST){ 
     UnionFind newU = new UnionFind(U); 
     newU.add(E); 
    } 

    printAllMsts(edgeNum+1, newU); 
} 

該算法的運行時間將取決於圖中的邊緣的數量和類型。對於問題的最壞情況輸入是當圖中所有邊都具有相同長度時。運行時間至少爲O（V * numberOfMsts），因爲只要存在不同MST的可能性，就會克隆當前的Union-Find數據結構，這需要花費O（V）時間。