UGC NET Computer Science December 2019 | Question 56

Question 56

---

The weight of minimum spanning tree in graph G. calculated using Kruskal's algorithm is:

Graph G

1. 1. 14
2. 2. 15
3. 3. 17
4. 4. 18

Explanation

Kruskal's algorithm is a MST(minimum-spanning-tree) algorithm., which finds an edge with the least possible edge weight that combines any two trees in the forest (initially all vertex are considered as separate tree).
Kruskal's algorithm follows the greedy algorithm approach in graph theory as it finds a MST for a connected weighted graph adding increasing cost edges at each step (Such that graph doesn't form a cycle).

Follow below steps to find MSP:
First Sorted edges by weight
2
3
4
5
6
7
8

We step by step only consider only edges from above sorted list such that it does not form cycle. The bold edges in above list will form a MST of graph in the order of increasing edge weight.

So, The weight of minimum spanning tree in graph G calculated using Kruskal's algorithm is :
= (2+3+4+6) = 15

Hence, Option 2 (15) is the right answer.

Previous	Next
UGC NET CS December 2019 - Q. 55	UGC NET CS December 2019 - Q. 57