Consider the following Adjacency matrix corresponding to some weighted Graph…
2017
Consider the following Adjacency matrix corresponding to some weighted Graph ‘G’.
What is the weight of the minimum spanning tree for the graph ‘G’?
- A.
8
- B.
9
- C.
10
- D.
11
Attempted by 95 students.
Show answer & explanation
Correct answer: B
The correct option is B.
Using Kruskal's algorithm, sort edges by weight: (3,4) weight 1, (1,5) weight 2, (2,5) weight 2, (2,3) weight 4. Selecting these edges covers all 5 vertices without creating a cycle. Total Minimum Spanning Tree (MST) weight = 1 + 2 + 2 + 4 = 9.
Loading lesson…