The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
1.3k views

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)}$

asked in Algorithms by Veteran (59.7k points)
edited by | 1.3k views
+4

$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.

+1

@Manu Thakur Sir pls help.. i dont understand y m i stuck with the answer of this simple problem !!!

+1
Sunny, they asked in the question "NOT" correct sequence.
0
I am so sorry to bother you .. i knew i wasmissing something... Thank you so much Sir :-)

1 Answer

+14 votes
Best answer

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.

answered by Boss (11.6k points)
edited by
+1
Same is the case with (A) where (e,f) 5 is added before (a,c) 3

Then why is it not wrong ?
+1
Option D

bcoz b-c (weight 4) is added before a-c (weight 3) ..In kruskal , weights are taken in ascending order..
+2

@Sankaranarayanan P.N

> So option D may be correct

D is one of the correct option.

Answer:

Related questions



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

44,301 questions
49,794 answers
164,407 comments
65,857 users