Virtual Gate Test Series: Algorithms - Minimum Spanning Tree

Question

I think all options are wrong

Comments

all are wrong options similar ques https://gateoverflow.in/3355/gate2008-it-45

---

https://gateoverflow.in/98214/virtual-gate
same question please merge this two

Answer 1

yup!

u r ryt . All options are wrong.

Comments

Option C is right answer

As edges with least weight are added to the existing tree to make the spanning tree grow. Every step, it remains a spanning tree but not a forest.

Answer 2

Yeah! All are wrong

Answer 3

https://stackoverflow.com/questions/1787152/prims-mst-does-the-start-node-matter  this show that you can start from any vertex

https://www.cse.ust.hk/~dekai/271/notes/L07/L07.pdf

refer to page 16

they are saying take any vertex and take the minimum edge to that vertices set that dont make cycle  repeat this step until you got all vertices

in option A    (c,d),(d,f) now taking (a,b) edge is wrong 

in option B    they started from the vertex e and grow and each step they took the minimum edge and at the time when choosing the third edge they can choose either of (b,f) and (c,d) they choose (b,f) and move ahead so this is right

in option C    they started from the vertex e and grow and each step they take the minimum edge and at the time when choosing the third edge they can choose either of (b,f) and (c,d) they choose (c,d) and move ahead this is right 

in option D   (d,f) now  taking(d,e ) is wrong

Comments

In option (B), (a, b) comes before (d, c)

---

because the weight of (a,b) is less than that of  (d,c)

---

I am saying should not (d, c) and (b, f) come together and (a, b) after that... And also write that you have considered 'e' as a source... I guess everyone taking 'd' as source vertex