31 31 votes Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm? $\text{(b, e) (e, f) (a, c) (b, c) (f, g) (c, d)}$ $\text{(b, e) (e, f) (a, c) (f, g) (b, c) (c, d)}$ $\text{(b, e) (a, c) (e, f) (b, c) (f, g) (c, d)}$ $\text{(b, e) (e, f) (b, c) (a, c) (f, g) (c, d)}$ Algorithms gatecse-2009 algorithms minimum-spanning-tree normal + – Kathleen 14.5k views answer comment Share Follow Print See all 6 Comments 6 6 Comments reply Show 3 previous comments Sunny Mukherjee commented Jan 31, 2018 reply Follow flag I am so sorry to bother you .. i knew i wasmissing something... Thank you so much Sir :-) 2 2 replyShare sameer_hack commented Jan 12, 2022 reply Follow flag Relatable xD 0 0 replyShare saismrutiranjan18 commented Sep 12 reply Follow flag https://youtu.be/LnF-dYhi8JE?si=ZKtRB3memPs898uR 0 0 replyShare Please log in or register to add a comment.
Best answer 37 37 votes In Option D $\text{ b-c}$ with weight, $4$ is added before $\text{a-c}$ with weight $3$ is added. In Kruskal's algorithm, edges should be added in non-decreasing order of weight. So, Option D may be correct. Sankaranarayanan P.N answered Oct 3, 2014 • edited Jun 25, 2018 by Pooja Khatri Sankaranarayanan P.N comment Share Follow See all 5 Comments 5 5 Comments reply Show 2 previous comments Chhotu commented Jul 29, 2017 reply Follow flag @Sankaranarayanan P.N > So option D may be correct D is one of the correct option. 2 2 replyShare pavansan commented Jan 6, 2025 reply Follow flag got it 0 0 replyShare Prashant-G commented May 14 reply Follow flag Because ef is 3 not 5 0 0 replyShare Please log in or register to add a comment.
2 2 votes Only sequence in option d is not possible.. chirudeepnamini answered Oct 13, 2019 chirudeepnamini comment Share Follow 0 reply Please log in or register to add a comment.
1 1 vote option d is right abhishekmehta4u answered Mar 23, 2019 abhishekmehta4u comment Share Follow 0 reply Please log in or register to add a comment.
0 0 votes D is not correct sequence as 4 is coming before 3 which is wrong ankit2024 answered Dec 23, 2025 ankit2024 comment Share Follow 0 reply Please log in or register to add a comment.
0 0 votes Similar or I would Exactly Same Question https://gateoverflow.in/1823/gate-cse-2006-question-47 Siddiqui_Danish answered Jan 7 Siddiqui_Danish comment Share Follow 0 reply Please log in or register to add a comment.
