edited by
8,869 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)}$

edited by

3 Answers

Best answer
26 votes
26 votes

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.

Answer:

Related questions

48 votes
48 votes
5 answers
3
Kathleen asked Sep 22, 2014
21,127 views
In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time com...