我正在尝试使用Heaps实现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)));
}
}
}
我已经看到它添加了所有顶点,并且最终像原始图一样,所以它不具有树属性。
为什么会这样?有人知道线索吗?非常感谢您的帮助。谢谢
我认为这是在创建循环,因为当你将边插入堆中时,你只会检查顶点是否处于"遍历"状态。在该插入和正在检索的相同边之间,可能已经从堆中检索到其他边,使得顶点已经链接到树。