Question 10669 – Minimum-Spanning-Tree
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 Spanning Tree?
Correct Answer: C
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) (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)