Prim's Algorithm

It is a greedy algorithm. It starts with an empty spanning tree. The idea is to maintain two sets of vertices:

• Contain vertices already included in MST.
• Contain vertices not yet included.

At every step, it considers all the edges and picks the minimum weight edge. After picking the edge, it moves the other endpoint of edge to set containing MST.

Steps for finding MST using Prim's Algorithm:

1. Create MST set that keeps track of vertices already included in MST.
2. Assign key values to all vertices in the input graph. Initialize all key values as INFINITE (∞). Assign key values like 0 for the first vertex so that it is picked first.
3. While MST set doesn't include all vertices.
1. Pick vertex u which is not is MST set and has minimum key value. Include 'u'to MST set.
2. Update the key value of all adjacent vertices of u. To update, iterate through all adjacent vertices. For every adjacent vertex v, if the weight of edge u.v less than the previous key value of v, update key value as a weight of u.v.

MST-PRIM (G, w, r)

 1. for each u ∈ V [G]
 2.     do key [u] ← ∞
 3.     π [u] ← NIL
 4.     key [r] ← 0
 5. Q ← V [G]
 6. While Q ? ∅
 7.     do u ← EXTRACT - MIN (Q)
 8.     for each v ∈ Adj [u]
 9.         do if v ∈ Q and w (u, v) < key [v]
 10.            then π [v] ← u
 11.            key [v] ← w (u, v)

Example: Generate minimum cost spanning tree for the following graph using Prim's algorithm.

Solution: In Prim's algorithm, first we initialize the priority Queue Q. to contain all the vertices and the key of each vertex to ∞ except for the root, whose key is set to 0. Suppose 0 vertex is the root, i.e., r. By EXTRACT - MIN (Q) procure, now u = r and Adj [u] = {5, 1}.

Removing u from set Q and adds it to set V - Q of vertices in the tree. Now, update the key and π fields of every vertex v adjacent to u but not in a tree.

Taking 0 as starting vertex  
  Root = 0  
    Adj [0] = 5, 1  
  Parent, π [5] = 0 and π [1] = 0  
      Key [5] = ∞ and key [1] = ∞  
  w [0, 5) = 10  and w (0,1) = 28  
   w (u, v) < key [5] , w (u, v) < key [1]  
        Key [5] = 10 and key [1] = 28  
So update key value of 5 and 1 is:

Now by EXTRACT_MIN (Q) Removes 5 because key [5] = 10 which is minimum so u = 5.

Adj [5] = {0, 4} and 0 is already in heap  
Taking 4, key [4] = ∞      π [4] = 5  
(u, v) < key [v] then key [4] = 25  
w (5,4) = 25  
w (5,4) < key [4]  
date key value and parent of 4.  

Now remove 4 because key [4] = 25 which is minimum, so u =4

Adj [4] = {6, 3}  
Key [3] = ∞         key [6] = ∞  
w (4,3) = 22        w (4,6) = 24  
w (u, v) < key [v]    w (u, v) < key [v]  
w (4,3) < key [3]      w (4,6) < key [6]  

Update key value of key [3] as 22 and key [6] as 24.

And the parent of 3, 6 as 4.

π[3]= 4       π[6]= 4   

u = EXTRACT_MIN (3, 6)            [key [3] < key [6]]  
u = 3              i.e.  22 < 24  

Now remove 3 because key [3] = 22 is minimum so u =3.

Adj [3] = {4, 6, 2}  
  4 is already in heap  
  4 ≠ Q key [6] = 24 now becomes key [6] = 18  
  Key [2] = ∞            key [6] = 24  
  w (3, 2) = 12          w (3, 6) = 18  
  w (3, 2) < key [2]         w (3, 6) < key [6]  

Now in Q, key [2] = 12, key [6] = 18, key [1] = 28 and parent of 2 and 6 is 3.

π [2] = 3      π[6]=3  

Now by EXTRACT_MIN (Q) Removes 2, because key [2] = 12 is minimum.

u = EXTRACT_MIN (2, 6)  
u = 2          [key [2] < key [6]]  
        12 < 18  
Now the root is 2   
Adj [2] = {3, 1}  
   3 is already in a heap  
Taking 1, key [1] = 28  
   w (2,1) = 16  
   w (2,1) < key [1]  

So update key value of key [1] as 16 and its parent as 2.

π[1]= 2  

Now by EXTRACT_MIN (Q) Removes 1 because key [1] = 16 is minimum.

Adj [1] = {0, 6, 2}  
    0 and 2 are already in heap.  
Taking 6, key [6] = 18  
   w [1, 6] = 14  
   w [1, 6] < key [6]  

Update key value of 6 as 14 and its parent as 1.

Π [6] = 1  

Now all the vertices have been spanned, Using above the table we get Minimum Spanning Tree.

0 → 5 → 4 → 3 → 2 → 1 → 6  
[Because Π [5] = 0, Π [4] = 5, Π [3] = 4, Π [2] = 3, Π [1] =2, Π [6] =1]

Thus the final spanning Tree is

Total Cost = 10 + 25 + 22 + 12 + 16 + 14 = 99