Prims algorithm

946 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 in which they are added to construct Minimum Spanning Tree (MST)?

1. P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T
2.   P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T
3.   P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T
4.   P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T
0
option-3 ?

option B

edited
0
Check option b after P-Q it is P-X in option not Q-X

Assuming you have knowledge of How prim algo works I have explained this answer.

(2)

The main thing is in prims algorithm is that when you at a node then you have to choose least weight edge unless it is not forming the cycle. Follow this rule you will get the correct answer as option B.

0
You are saying about kruskal.  ???

Related questions

1
2.2k views
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ? Any example which favours this ?
1 vote
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$