search
Log In
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.
in Algorithms 299 views
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

Please log in or register to answer this question.

Related questions

2 votes
3 answers
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
asked Nov 17, 2017 in Algorithms Parshu gate 780 views
3 votes
1 answer
2
1.5k views
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$
asked Sep 22, 2017 in Algorithms pC 1.5k views
3 votes
2 answers
3
2.1k 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 ?
asked Jan 24, 2017 in Algorithms Kapil 2.1k views
0 votes
0 answers
4
750 views
I am getting B and C both. Answer is given as C. Where am I wrong?
asked Jan 24, 2017 in Algorithms Samujjal Das 750 views
...