The Gateway to Computer Science Excellence
–1 vote
304 views

I think all options are wrong

in Algorithms by Active (3k points)
edited by | 304 views
0
https://gateoverflow.in/98214/virtual-gate
same question please merge this two

3 Answers

+2 votes
yup!

u r ryt . All options are wrong.
by Active (1.2k points)
+2
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.
0 votes
Yeah! All are wrong
by (447 points)
0 votes

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

by Boss (10.6k points)
0
tell me reason why i got negative vote so that i shall not do it again
0
and it is very easy to negative vote before reading the explaination if you really read my explanation than first you told me what is wrong and than you should vote
0

https://gateoverflow.in/3355/gate2008-it-45 goto this who are not able to understand

0
In option (B), (a, b) comes before (d, c)
0
because the weight of (a,b) is less than that of  (d,c)
0
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
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,258 answers
198,087 comments
104,737 users