in Algorithms edited by
7,698 views
20 votes
20 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? 

  1. $(a-b),(d-f),(b-f),(d-c),(d-e)$
  2. $(a-b),(d-f),(d-c),(b-f),(d-e)$
  3. $(d-f),(a-b),(d-c),(b-f),(d-e)$
  4. $(d-f),(a-b),(b-f),(d-e),(d-c)$
in Algorithms edited by
7.7k views

1 comment

First sort the edges on the basis of their weight ... Then Apply disjoint set operations ....
2
2

2 Answers

26 votes
26 votes
Best answer

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$

edited by

2 Comments

How can b-f possible??
0
0

@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) 

                           

1
1
1 vote
1 vote

In all the possible ways, edge d-e is added at the end.. So option d is wrong..

Answer:

Related questions