1 votes 1 votes 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. Algorithms prims-algorithm algorithms + – just_bhavana asked Oct 30, 2017 just_bhavana 842 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Rupendra Choudhary commented Oct 30, 2017 reply Follow Share 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. 0 votes 0 votes Rupendra Choudhary commented Oct 30, 2017 reply Follow Share 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. 1 votes 1 votes just_bhavana commented Oct 30, 2017 reply Follow Share I think the question meant to ask for connectedness! thanks 0 votes 0 votes Shubhanshu commented Oct 30, 2017 reply Follow Share @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" 1 votes 1 votes just_bhavana commented Oct 31, 2017 reply Follow Share yes, got it. Thanks @Shubhanshu 0 votes 0 votes Please log in or register to add a comment.
