The Gateway to Computer Science Excellence
+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.
in Algorithms by Boss (12.1k points) | 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

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,252 answers
198,062 comments
104,698 users