25 votes 25 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 spanning-tree normal + – Kathleen asked Sep 22, 2014 edited Apr 29, 2021 by S k Rawani Kathleen 8.9k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Manu Thakur commented Dec 27, 2017 i edited by Manu Thakur Jan 31, 2018 reply Follow Share $Remark:$ In Kruskal's algorithm, Edges are sorted in ascending order in O(ElogE) time. Any edge with larger weight can't be added before an edge with the smaller weight. (D) is the correct choice, b-c can't added before a-c. 11 votes 11 votes Sunny Mukherjee commented Jan 31, 2018 reply Follow Share @Manu Thakur Sir pls help.. i dont understand y m i stuck with the answer of this simple problem !!! 1 votes 1 votes Manu Thakur commented Jan 31, 2018 reply Follow Share Sunny, they asked in the question "NOT" correct sequence. 3 votes 3 votes Sunny Mukherjee commented Jan 31, 2018 reply Follow Share I am so sorry to bother you .. i knew i wasmissing something... Thank you so much Sir :-) 1 votes 1 votes sameer_hack commented Jan 12, 2022 reply Follow Share Relatable xD 0 votes 0 votes Please log in or register to add a comment.
Best answer 26 votes 26 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 3 Comments See all 3 3 Comments reply Arunav Khare commented Apr 1, 2017 reply Follow Share Same is the case with (A) where (e,f) 5 is added before (a,c) 3 Then why is it not wrong ? 1 votes 1 votes S Harika commented Apr 1, 2017 reply Follow Share Option D bcoz b-c (weight 4) is added before a-c (weight 3) ..In kruskal , weights are taken in ascending order.. 1 votes 1 votes Chhotu commented Jul 29, 2017 reply Follow Share @Sankaranarayanan P.N > So option D may be correct D is one of the correct option. 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes option d is right abhishekmehta4u answered Mar 23, 2019 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Only sequence in option d is not possible.. chirudeepnamini answered Oct 13, 2019 chirudeepnamini comment Share Follow See all 0 reply Please log in or register to add a comment.