Error in Prim's algorithm implementation, Empty Heap

Question

I am trying to implement Prim's minimum spanning tree algorithm using Heaps. However, as I execute my code I get an exception, that the heap is empty.

After some iterations, it says that heap is empty. This is the main loop of my algorithm:

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);

        }

And my getAdjacent method is:

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)));
        }

    }
}

I have seen that it adds al vertices and ends up like the original graph, so it doesnt mantain the tree property.

Why is this? Anyone has a clue? Help would be very appreciated. Thanks!

Answer 1

I think it's creating loops because you're only checking whether a vertex is in `traversed' when you insert an edge into a heap. In between that insertion and the same edge being retrieved, other edges may have been retrieved from the heap such that the vertex is already linked to the tree.