25 votes 25 votes Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree? $\text{(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)}$ $\text{(A, D), (A, B), (A, C), (C, F), (G, E), (F, G)}$ $\text{(A, B), (A, D), (D, F), (F, G), (G, E), (F, C)}$ $\text{(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)}$ Algorithms gateit-2004 algorithms graph-algorithms normal prims-algorithm + – Ishrat Jahan asked Nov 2, 2014 • retagged Jan 2 by Hira Thakur Ishrat Jahan 14.4k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Bhagirathi commented Nov 20, 2014 reply Follow Share I found out that the option D is the correct possible order by trial and error method. 1 votes 1 votes Tuhin Dutta commented Apr 9, 2018 reply Follow Share At each step Prim's algo adds to the tree an edge that contributes the min amount possible to the tree's weight but Kruskal's algo adds to the forest an edge of least possible weight. A) (E, G), (C, F): the last edge is not added to the tree. B) (A, D), (A, B), (A, C), (C, F), (G, E): the last edge is not added to the tree. C) (A, B), (A, D): Edge weight (A,B) > (A,D), so (A,B) should come after (A,D) not before. D) Obvious choice. 6 votes 6 votes Akash 15 commented Jan 4 reply Follow Share $Ans: D$ 0 votes 0 votes ritiksri8 commented Mar 21 reply Follow Share Answer will be (D) in this case as option B fails to make graph connected. 0 votes 0 votes Please log in or register to add a comment.
Best answer 34 votes 34 votes Answer is D. $A$ and $B$ produce disconnected components with the GIVEN order in options which is NEVER allowed by prims's algorithm. $C$ produces connected component every instant a new edge is added BUT when first vertex is chosen(first vertex is chosen randomly) first edge must be the minimum weight edge that is chosen . Therefore, $(A,D)$ MUST be chosen BEFORE $(A,B)$. Therefore, $C$ is FALSE. Sandeep_Uniyal answered Jan 17, 2015 • edited Jun 12, 2018 by Milicevic3306 Sandeep_Uniyal comment Share Follow See all 2 Comments See all 2 2 Comments reply junk_mayavi commented Nov 4, 2017 reply Follow Share while extracting from min heap, if two nodes comes with same key value, which one to choose ? what i understood is , heap sort is never in-place and we can't predict which min key node appears as root. in that case, we need to try with both the min key values, isn't it ? 1 votes 1 votes chirudeepnamini commented Oct 14, 2019 reply Follow Share I think the correct reason for eliminating option c would be "After selecting DF, we should select FC(having weight 4) but we are selecting FG(having weight 5) which is not the minimum". 4 votes 4 votes Please log in or register to add a comment.
9 votes 9 votes There are two correct sequences i) (A, D), (A, B), (A, C), (C, F), (F, G), (G, E) (not given in the options) ii) (A, D), (A, B), (D, F), (F, C), (F, G), (G, E) Option- D Sourav Basu answered Dec 21, 2017 Sourav Basu comment Share Follow See all 5 Comments See all 5 5 Comments reply Sunny Mukherjee commented Feb 1, 2018 reply Follow Share yup !!! 0 votes 0 votes Chandrabhan Vishwa 1 commented Dec 26, 2018 reply Follow Share b is not correct. because in between step disconnect tree it is created . 0 votes 0 votes ankit3009 commented Jan 10, 2021 reply Follow Share how disconnected graph is created in b? it seems correct to me can anyone please explain. 0 votes 0 votes Ray Tomlinson commented Jul 26, 2023 reply Follow Share 1 st sequence is wrong bcoz it forms cycle 0 votes 0 votes sitikant commented Aug 27, 2023 reply Follow Share The option B sequence should end with (F,G), (G,E) not the other way. That's why it is false. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes According to Prim's Algorithms Correct Answer is D Anand Maurya answered Jun 21, 2019 Anand Maurya comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Here 2 different Answers are possible . in the first image we visited vertex $C$ firstly before vertex $F$ then we get the answer which does not match with anyone of them and this is wrong answer bcoz it makes cycle iin the second image we visited vertex $F $ firstly before vertex $C$ then we get the answer which does match with option D so the final answer is option D Ray Tomlinson answered Jul 26, 2023 • edited Jul 26, 2023 by Ray Tomlinson Ray Tomlinson comment Share Follow See all 0 reply Please log in or register to add a comment.