UGC NET CSE | Junet 2015 | Part 2 | Question: 21

Question

Consider the given graph

Its Minimum Cost Spanning Tree is ______

• A.
• B.
• C.
• D.
• E.
• F.
• G.
• H.

 

 

 

Comments

B. Is ans...

Option A and C is eliminated since not having 1-6 edge...

D is eliminated since it contains edge weight 28 Even we have choice for smaller edge weight...

Answer 1

finding MST using Kruskal’s algorithm steps as follow:

1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
3. continue step 2 until we have (V-1) edges in the spanning tree.