The Gateway to Computer Science Excellence
+16 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?

  1. $\text{(b, e) (e, f) (a, c) (b, c) (f, g) (c, d)}$

  2. $\text{(b, e) (e, f) (a, c) (f, g) (b, c) (c, d)}$

  3. $\text{(b, e) (a, c) (e, f) (b, c) (f, g) (c, d)}$

  4. $\text{(b, e) (e, f) (b, c) (a, c) (f, g) (c, d)}$

in Algorithms by Veteran (52.2k points)
edited by | 1.8k views

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.


@Manu Thakur Sir pls help.. i dont understand y m i stuck with the answer of this simple problem !!!

Sunny, they asked in the question "NOT" correct sequence.
I am so sorry to bother you .. i knew i wasmissing something... Thank you so much Sir :-)

3 Answers

+18 votes
Best answer

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.

by Boss (11k points)
edited by
Same is the case with (A) where (e,f) 5 is added before (a,c) 3

Then why is it not wrong ?
Option D

bcoz b-c (weight 4) is added before a-c (weight 3) ..In kruskal , weights are taken in ascending order..

@Sankaranarayanan P.N

> So option D may be correct

D is one of the correct option.

0 votes

option d is right

by Boss (36.5k points)
0 votes

Only sequence in option d is not possible..

by Active (4.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
104,693 users