Data Structures and Algorithms |
Prim's Algorithm |
Prim's algorithm works efficiently if we keep a
list d[v] of the cheapest weights which connect
a vertex, v, which is not in the tree,
to any vertex already in the tree.
A second list pi[v] keeps the index of the
node already in the tree to which v
can be connected with cost, d[v].
int *MinimumSpanningTree( Graph g, int n, double **costs ) {
Queue q;
int u, v;
int d[n], *pi;
q = ConsEdgeQueue( g, costs );
pi = ConsPredList( n );
for(i=0;i<n;i++) {
d[i] = INFINITY;
}
/* Choose 0 as the "root" of the MST */
d[0] = 0;
pi[0] = 0;
while ( !Empty( q ) ) {
u = Smallest( g );
for each v in g->adj[u] {
if ( (v in q) && costs[u][v] < d[v] ) {
pi[v] = u;
d[v] = costs[u][v];
}
}
}
return pi;
}
The steps are:
The time complexity is O(VlogV + ElogV) = O(ElogV), making it the same as Kruskal's algorithm. However, Prim's algorithm can be improved using Fibonacci Heaps (cf Cormen) to O(E + logV).
Key terms |
The time complexity is O(VlogV + ElogV) = O(ElogV), making it the same as Kruskal's algorithm. However, Prim's algorithm can be improved using Fibonacci Heaps (cf Cormen) to O(E + logV).
Proving the MST algorithm | Graph Representations | Back to the Table of Contents |