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)}$
$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.
@Manu Thakur Sir pls help.. i dont understand y m i stuck with the answer of this simple problem !!!
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
> So option D may be correct
D is one of the correct option.
option d is right
Only sequence in option d is not possible..