in Algorithms edited by
8,821 views
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?

  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 edited by
8.8k views

4 Comments

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

3 Answers

26 votes
26 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.

edited by

3 Comments

Same is the case with (A) where (e,f) 5 is added before (a,c) 3

Then why is it not wrong ?
1
1
Option D

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

@Sankaranarayanan P.N

> So option D may be correct

D is one of the correct option.

2
2
0 votes
0 votes

option d is right

0 votes
0 votes

Only sequence in option d is not possible..

Answer:

Related questions