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).
© John Morris, 1998
Proving the MST algorithm
Graph Representations
Back to the Table of Contents