The heart of Prim's algorithm for finding minimal spanning trees is
given below (enough to reason about the complexity), the entire
program that calculates the tree is in prim.cpp
What is the complexity of this algorithm on a graph with V
vertices and E edges? You should write an expression in
terms of both E and V, e.g., something like O(E
+ V log V). Assume that the priority queue never has more than
V elements in it.
<![CDATA[
tpqueue<VertDist> pq;
int k;
tvector<string> verts, adj;
// insert all vertices into priority queue with distances
// of infinity, except for vertex 0 which has distance 0
int vertex;
VertDist vd;
while (pq.size() > 0) {
pq.deletemin(vd);
vertex = vd.vertex;
if (!myState[vertex].visited) {
myState[vertex].visited = true;
myGraph.getAdjacent(myGraph.getName(vertex), adj);
for(k=0; k < adj.size(); k++) {
int index = myGraph.getNum(adj[k]);
if (! myState[index].visited) {
double weight = myGraph.getWeight(vertex, index);
if (weight < myState[index].distance) {
myState[index].distance = weight;
myState[index].path = vertex;
pq.insert(VertDist(index,myState[index].distance));
}
}
}
}
}
]]>