Prim's and Kruskal's Algorithms for Minimum Spanning Tree

Prim’s Algorithm Algorithm 1. Select an edge of graph G that has the smallest weight  value and add it to the tree 2. Now select another edge from G which is not present in  T but it is adjacent to a node present in T and having  minimum weight value. 3. Add this new edge to tree T iff it does not form cycle 4. Repeat steps 2 and 3 till all the nodes are included in T.

1 3 2 5 4 2 6 4        7                  5 3                    5

1. Select an edge with minimum  weight value. 1. T={1,5} weight=2 2. Remaining edges adjacent to 1 and 5 are{(1,2), (1, 3) (5, 3), (5,4)} 6            4           7            5 2. Select an edge with minimum weight value that is (1,3) T={1,3,5}  weight is=4+2=6                           2 4              4 1 5 3

 3. now consider edges adjacent  to 1, 3 and 5 and not present in  T (1,2) (5,3) (5,4) (3,2) (3,4) 6           7         5         3         5 Select an edge of minimum weight which does not form cycle that  is(3,2)T={1,3,5,2}                                           2            4 3 Now weight is=2+4+3=9 1 5 3 2

 3. now consider edges adjacent  to 1,2, 3 and 5 and not present in T (1,2) (5,3) (5,4) (3,4) 6      7      5        5 Select an edge of minimum weight which does not form cycle that  is(5,4)T={1,3,5,2,4} 2 4 3 5 Now weight is = 2+4+3+5=14 1 5 3 2 4

Kruskal’s Algorithm 1. select an edge of graph G that has the smallest value and add it  to tree T.2. Now select another edge from G which is not present in T but  having minimum weight value.3. Add this new edge to T only if it does not form a cycle.4. Repeat step 2 and 3 till all edges of G are included in T.  

V={1,2,3,4,5} E={(1,5)(3,4)(5,4)(2,3),(1,2)(5,3)(1,3)} select an edge with minimum weight value  that is(1,5) 1 5 3 2 4

2 T={1, 5} weight={2} 1 5 3 2 4

2 4 T={1, 5,3,4} weight={2+4}=6 1 5 3 2 4

 3 2 4 T={1, 5,3,4,2} weight={2+4+3=9} 1 5 3 2 4

2 5 4                            3 T={1, 5,3,4,2} weight={2+4+3+5=14} 1 5 3 2 4