edited by
9,565 views
21 votes
21 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)$
edited by

2 Answers

Best answer
26 votes
26 votes

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$

Answer:

Related questions

32 votes
32 votes
7 answers
1
Rucha Shelke asked Sep 16, 2014
14,631 views
Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanni...
90 votes
90 votes
12 answers
2
59 votes
59 votes
7 answers
3
Rucha Shelke asked Sep 16, 2014
31,356 views
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:QueueStackHeapB-Tree