search
Log In
–1 vote
385 views

I think all options are wrong

in Algorithms
edited by
385 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.
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
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

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

Related questions

3 votes
0 answers
2
2 votes
0 answers
4
386 views
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges to which they are added to construct Minimum Spanning Tree (MST)? P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T PLEASE EXPLAIN.
asked Jan 8, 2018 in Algorithms ankit_thawal 386 views
...