###### Question 10740 – Minimum-Spanning-Tree
February 13, 2024
###### Question 3269 – 2016 July NTA UGC NET Paper 1
February 13, 2024
###### Question 10740 – Minimum-Spanning-Tree
February 13, 2024
###### Question 3269 – 2016 July NTA UGC NET Paper 1
February 13, 2024

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim’s algorithm to construct a Minimum Span­ning Tree?

Question 12 Explanation:
Prim’s algorithm starts from any vertex and expands MST by adding one vertex in each step which is close to the intermediate MST (made till previous step).
(A) (d, f) is chosen but neither ‘d’ nor ‘f’ vertices are part of previous MST (MST made till previous step).
(B) (g, h) is chosen but neither g or h vertices are part of MST made till previous step.
(C) Correct.
(D) (f, c) is chosen, but at that point (f, d) had less weight. So, (f , d) should have been chosen.
(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)
(c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)
(d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)
(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)