Back

Table of contents

Next

Prim's Algorithm

  Prim's algorithm operates much like Dijkstra's algorithm for finding shortest paths in a graph. As illustrated in the applet , the tree starts from an arbitrary root vertex r and grows  until the tree spans all the vertices in V. At each step a light edge connecting a vertex in A to a vertex in  V - A is added to the tree. This strategy is "greedy".

   In the pseudocode below, the graph G and the root r of the minimum spanning treeto be grown are inputs to the algorithm. During execution of the algorithm, all the vertices that are not in the tree reside in a priority queue Q based on a key field. For each vertex v, key[v] is the minimum weight of any edge connecting v to a vertex in the tree; by convention key[v] = infinity if there is no dsuch edge.During the algorithm, the set A from GENERIC-MST is kept implicitly as

A = { ( v, parent[v]) : v belongs to V - { r } - Q} .

When the algorithm terminates, the priority queue Q is empty: the minimum spanning tree A for G is thus
 
A = { ( v. parent[v]) : v belongs to V - { r } ).

MST-PRIM(G, w, r)

   1   Q <- V[G]
   2   for each u belonging to Q
   3           do key[u] <- inf
   4    key[r] <- 0
   5   parent[r] <- NULL
   6   while Q != empty
   7          do u <- EXTRACT-MIN(Q)
   8                 for each v belonging to Adj[u]
   9                      do if v belongs to Q and w(u, v) < key[v]
  10                               then parent[v] <- u
  11                                        key[v] <- w(u, v)
 

   Lines 1-4 initialize the priority queue Q to contain all the vertices and set the key of each vertex to infinity, except for the root whose key is set to 0.Througout the algorithm, the set V - Q contains the vertices in the tree being grown. Line 7 identifies a vertexs v belonging to Q incident on a light edge crossing the cut (V - Q, Q). Removing u from the set Q adds it to the set V - Q of vertices in the tree. Lines 8-11 update the key and parent fields of every vertex v adjacent to u but not in the tree.
 
    The performance of Prim's algorithm depends on how we implement the priority queue Q. If Q is implemented as a binary heap, we can use the BUILD-HEAP procedure to perform the initializations in lines 1-4 in O(V) time. The loop is executed | V | times, and since