#Algorithms #Mst Reference to Gate 2008 Question

Question

Link to actual Question - https://gateoverflow.in/3355/gate2008-it-45?show=214096#c214096

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span­ning Tree?

B) (c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)

===================================

is this explanation of option (b) valid ? 

as we're starting from vertex c then we will choose the minimum edge from all the adjacent vertices of c. 

So, here (c,e) = 7 is chosen before (c,f) which is 3 and that makes it false b/c (c,f) should be chosen first.

Answer 1

• prims algorithm always gives connected graph.
• kruskal algorithm may or may not be connectrd

but in option a and b both gives disconnected graph so it is false.

Comments

arnav . bro we take starting vertex e . and run prims algo. and write down the edges in which order you select. and match the option .

---

Thanks bhai, samaj gaya! :)

Thank you and you're a hero!

---

u r also hero bro.

i also read ur comment which are nicelly explained