25 votes 25 votes What is the weight of a minimum spanning tree of the following graph? $29$ $31$ $38$ $41$ Algorithms gatecse-2003 algorithms minimum-spanning-tree normal + – Kathleen asked Sep 17, 2014 • edited May 1, 2021 by gatecse Kathleen 7.8k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 23 votes 23 votes Apply Prim's algorithm, start from $A$ as shown in figure below. Add all the weights in the given figure which will be equal to $31$. Correct Answer: $B$ monanshi answered Jan 14, 2016 • edited May 8, 2021 by gatecse monanshi comment Share Follow See all 6 Comments See all 6 6 Comments reply Vicky rix commented Dec 17, 2017 reply Follow Share yes prims is easier to apply than kruskal here ... 0 votes 0 votes lakshaysaini2013 commented Aug 31, 2018 reply Follow Share what if we apply the kruskal here? 1 votes 1 votes vishalshrm539 commented Oct 15, 2018 reply Follow Share @lakshaysaini2013 Nothing, answer will be same, you just have to avoid any cycle/loop. 1 votes 1 votes `JEET commented Dec 24, 2019 reply Follow Share Can we backtrack in a prims algorithm?? I mean if we can't move ahead on any edge, then can we backtrack? 0 votes 0 votes `JEET commented Dec 24, 2019 reply Follow Share @techbd123 Can you please see my above comment. 0 votes 0 votes techbd123 commented Dec 25, 2019 reply Follow Share @`JEET Please check it. 1 votes 1 votes Please log in or register to add a comment.
4 votes 4 votes Solution: B The minimum spanning tree is AC,AD,BG,EI,BD,FH,HI,IJ,GH. Gowthaman Arumugam answered Feb 2, 2015 Gowthaman Arumugam comment Share Follow See 1 comment See all 1 1 comment reply Kaluti commented Oct 8, 2017 reply Follow Share answer is 31 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Use kruskals algorithm 31 is the answer shashankrustagi answered Dec 10, 2020 shashankrustagi comment Share Follow See all 0 reply Please log in or register to add a comment.