retagged by
496 views

2 Answers

1 votes
1 votes

ANSWER MUST BE SEQUENCE 2.....

one point question is checking ......

"we should know that during prims algo we always encountered a tree...but in the Kruskals we may get forest or disconnected components ....."

here in option 1)after a,b,c,d points we must get next and edge from any of these vertex...but we got it as E-F...not possible....

2)it holds correct sequence ....here it is not creating cycle...and also...edges are added only form vertices which are visited ...so it must be answer..

3)after vertex c,e,f,d....we must get an edge from these vertex only ...but we get A-B...again fails 

"one more point =all above sequences can be possible in KRUSKALS ALGO..."

0 votes
0 votes

While we apply prim algo, it always gives connected graph.

option 1: (a,b),(b,c),(a,d),(e,f){here it get disconnected},(d,g),(c,e)

option 2: (g,f),(f,c),(g,d),(c,e),(d,b),(d,a) {always connected}

option 3: (c,f),(c,e),(e,d),(a,b){here it get disconnected},(d,g),(b,c)

hence, option 2 is correct.

Related questions

0 votes
0 votes
1 answer
1
anonymous asked Jun 26, 2016
643 views
3 votes
3 votes
1 answer
3
pC asked Sep 22, 2017
2,508 views
Explain Prims AlgorithmAnalysis Of Time ComplexityHow does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$