Prim算法實現中的錯誤，空堆

我正在嘗試使用堆實現Prim的最小生成樹算法。但是，當我執行我的代碼時，我得到一個異常，堆是空的。Prim算法實現中的錯誤，空堆

經過一番迭代，它說堆是空的。這是我的算法的主循環：

while(traversed.size() < n){ 
      Edge optimal = heap.minElem(); 
      heap.delMin(); 
      traversed.add(optimal.getDest()); 
      mst.set(optimal.getSource().getVertex(), optimal.getDest().getVertex(), optimal.getDist()); 
      mst.set(optimal.getDest().getVertex(), optimal.getSource().getVertex(), optimal.getDist()); 
      //now compute further adjacent 
      getAdjacent(optimal.getDest(),myGraph,heap,traversed); 

     }

而且我getAdjacent方法是：

private void getAdjacent(Vertex v, CGraph graph, Heap<Edge> heap, Set<Vertex> traversed) throws Exception{ 
int val; 
for(int i = 0; i < graph.numV; i++){ 
    val = graph.get(v.getVertex(), i); 
    if((val != 0) && (val != CGraph.Infinity) && !(traversed.contains(new Vertex(i)))){ 
     heap.insert(new Edge(graph.get(v.getVertex(),i),v, new Vertex(i))); 
     } 

    } 
}

我已經看到，它增加了人的頂點和像原來的圖形結束了，所以它不十個分量樹屬性。

這是爲什麼？任何人都有線索？幫助將非常感激。謝謝！

來源

2013-12-09 Felipe Sulser

如果它從不*向堆中添加頂點，那麼爲什麼算法在第一次迭代之後不會失敗？如果你能給出一些失敗的圖的例子，堆中的頂點，每一步的遍歷和mst，它都會有所幫助。 –

我已更新代碼，現在它返回原始圖形。感謝您的關注 –

我認爲這是創建循環，因爲您只是在將邊緣插入堆時檢查頂點是否處於「遍歷」狀態。在該插入與正被檢索的相同邊緣之間，可能已從堆中檢索到其他邊緣，使得頂點已經鏈接到樹。

來源

2013-12-10 18:22:23

謝謝！我現在已經解決了。 –

Prim算法實現中的錯誤，空堆

回答

相關問題