32 32 votes Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm? $(a-b),(d-f),(b-f),(d-c),(d-e)$ $(a-b),(d-f),(d-c),(b-f),(d-e)$ $(d-f),(a-b),(d-c),(b-f),(d-e)$ $(d-f),(a-b),(b-f),(d-e),(d-c)$ Algorithms gatecse-2006 algorithms graph-algorithms minimum-spanning-tree normal + – Rucha Shelke 14.0k views answer comment Share Follow Print See 1 comment 1 1 comment reply Puja Mishra commented Jan 10, 2018 reply Follow flag First sort the edges on the basis of their weight ... Then Apply disjoint set operations .... 4 4 replyShare Please log in or register to add a comment.
Best answer 37 37 votes In Kruskal's algo the edges are added in non decreasing order of their weight. But in Option D edge $d-e$ with weight $3$ is added before edge $d-c$ with weight $2$. Hence, option D is wrong option. Correct Answer: $D$ Sankaranarayanan P.N answered Oct 3, 2014 • edited Apr 29, 2019 by Naveen Kumar 3 Sankaranarayanan P.N comment Share Follow See all 3 Comments 3 3 Comments reply Kanishk251296 commented Sep 27, 2018 reply Follow flag How can b-f possible?? 0 0 replyShare air1ankit commented Nov 27, 2018 reply Follow flag @Kanishk251296 (d - f) = 1 (a - b) = 1 (b - f) = 2 (d - e) = 3 (d - c) = 2 In kruskal's algo the edges are added in non decreasing order of their weight. but (d - e) added before (d - c) 3 3 replyShare pavansan commented Jan 6, 2025 reply Follow flag got it 1 1 replyShare Please log in or register to add a comment.
3 3 votes In all the possible ways, edge d-e is added at the end.. So option d is wrong.. chirudeepnamini answered Oct 13, 2019 chirudeepnamini comment Share Follow 0 reply Please log in or register to add a comment.
0 0 votes in short we have to remember for this type of question ascending order also must satisfy for MST Verify ? ankit2024 answered Dec 23, 2025 ankit2024 comment Share Follow See 1 comment 1 1 comment reply rojje commented Dec 26, 2025 reply Follow flag yes 0 0 replyShare Please log in or register to add a comment.
