The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 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)$
asked in Algorithms by Active (3.7k points) | 1.1k views
First sort the edges on the basis of their weight ... Then Apply disjoint set operations ....

1 Answer

+17 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.

answered by Boss (11.5k points)
edited by
How can b-f possible??

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,744 questions
47,464 answers
62,227 users