Question

Question 3 Apply Kruskal's algorithm to find Minimum Spanning Tree for the following graph. (In the final exam, you might be asked about Prim's algorithm or both). Weight of edge(1,2) = 10 Weight of edge(2,4)= 5 Weight of edge(6,4)=10 Weight of edge(1,4) = 20 Weight of edge(2,3) = 3 Weight of edge(6,5)= 3 Weight of edge(1,6) = 2 Weight of edge(3,5) = 15 Weight of edge(4,5)= 11

Answer 1

Given Graph is

Kruskal’s Algorithm to find the Minimum Cost Spanning Tree (MCST) of a graph G as follows:

Here consider those edges in each step which are minimum and doesnot form Loops

Step 1:                                                                 

Step 2:                                               

Step 3:

Step 4:                                                                 

Step 5:

For n- Vertices we get (n-1) Edges in MCST. Here in graph having 6 Vertices so we get 5 Edges

Which is Required MCST of a graph