+1 vote
250 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.
| 250 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