# Prim's algorithm for MST

1 vote
299 views
Assuming that the graph can contain repeated edge weights, we have a single tree at any instance when applying Prim's algorithm.

Justify this statement.
0
what do you mean by single tree?

if edge weights are repeated then we may have more than one MST that corresponds to minimum weight , doesn't matter which algorithm you're following.

if by single tree , you mean only One MST then statement is false.
1
if by single tree you mean 'only one connected tree' then yes! prime's aglo always create a connected tree during MST calculation (doesn't matter edge weights are repeated or not) while kruskal's algo may generate non-connected trees during Process of MST generation.
0
I think the question meant to ask for connectedness! thanks
1

@just_bhavana, consider the following line carefully

we have a single tree at any instance when applying Prim's algorithm.

Keyword - at any instance

According to CLRS - "Prims Algorithm will always generate connected tree at any instance of time during the process of generation of MST but Kruskal may give forest(a collection of disconnected trees) or a single tree"

0
yes, got it. Thanks @Shubhanshu

## Related questions

1
780 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)? 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 P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$