1.4k views

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)$
+1
First sort the edges on the basis of their weight ... Then Apply disjoint set operations ....

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
0
How can b-f possible??
0

(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
2