to be honest..OOP style is the least of my worries..as long as I get this algorithm working..
but when you were doing the Prim's did you ever after removing from the heap array..did you ever set the weight to a minimum value or so?
Any way here is one algorithm from the internet
Code:
While P is not empty:
1. Select the next vertex u to add to the tree
u = P.deleteMin()
2. Update the weight of each vertex w adjacent to u which is not in the tree (i.e., w P)
If weight(u,w) < D(w),
a. parent(w) = u
b. D(w) = weight(u,w)
c. Update the priority queue to reflect
new distance for w
Lecturers algorithm..possibly from wikipedia
Code:
Prim_Sparse( Vertex s )
Begin
// G = (V, E)
for each v in V
dist[v] = INT_MAX (infinity)
parent[v] = 0 // treat 0 as a special null vertex
hPos[v] = 0 // indicates that v heap
h = new Heap // priority queue (heap) initially empty
h.insert(s) // s will be the root of the MST
while (not h.isEmpty() ) // should repeat |V|-1 times
v = h.remove() // add v to the MST
dist[v] = -dist[v] // marks v as now in the MST
for each u in adj(v) // examine each neighbour u of v
if wgt(v, u) < dist[u]
dist[u] = wgt(v, u)
parent[u] = v
if u is not an element of the heap
h.insert( u)
else
h.siftUp( hpos[u])
end if
end for
end w
return parent
it doesn't say to reset the distance...:S