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 spanning-tree normal + – Kathleen asked Sep 17, 2014 edited May 1, 2021 by gatecse Kathleen 7.5k 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 Show 3 previous comments `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.