GATE IT 2004 | Question: 56

Question

Consider the undirected graph below:

Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?

• A. $\text{(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)}$
• B. $\text{(A, D), (A, B), (A, C), (C, F), (G, E), (F, G)}$
• C. $\text{(A, B), (A, D), (D, F), (F, G), (G, E), (F, C)}$
• D. $\text{(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)}$

Comments

$Ans: D$

---

Answer will be (D) in this case as option B fails to make graph connected.

---

no. if we start from vertex B then AB,AD is the only correct order. so no problem in these 2 atleast.

Answer 1

Answer is D.

$A$ and $B$ produce disconnected components with the GIVEN order in options which is NEVER allowed by prims's algorithm.

$C$ produces connected component every instant a new edge is added BUT when first vertex is chosen(first vertex is chosen randomly) first edge must be the minimum weight edge that is chosen . Therefore, $(A,D)$ MUST be chosen BEFORE $(A,B)$. Therefore,  $C$ is FALSE.

Comments

while extracting from min heap, if two nodes comes with same key value, which one to choose ?  

what i understood is , heap sort is never in-place and we can't predict which min key node appears as root. in that case, we need to try with both the min key values, isn't it ?

---

I think the correct reason for eliminating option c would be "After selecting DF, we should select FC(having weight 4) but we are selecting FG(having weight 5) which is not the minimum".

Answer 2

There are two correct sequences

i) (A, D), (A, B), (A, C), (C, F), (F, G), (G, E)  (not given in the options)

ii) (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)  Option- D

Comments

how disconnected graph is created in b? it seems correct to me can anyone please explain.

---

1 st sequence is wrong bcoz it forms cycle

---

The option B sequence should end with (F,G), (G,E) not the other way. That's why it is false.

Answer 3

According to Prim's Algorithms Correct Answer is D

Answer 4

 

Here 2 different Answers are possible .

 

in the first image we visited vertex $C$ firstly before vertex $F$ then we get the answer which does not match with anyone of them and this is wrong answer bcoz it makes cycle

iin the second image we visited vertex $F $  firstly before vertex  $C$ then we get the answer which does  match with option D 

 

so the final answer is option D