menu
search
Log In
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

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

GATE2009-38

19 votes
3.7k 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)}$

in Algorithms
edited by 3.7k views
8

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


edited by
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 :-)

3 Answers

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


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.

0 votes

option d is right

0 votes

Only sequence in option d is not possible..

← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →
Answer:

Related questions

40 votes
3 answers
1
6.3k views
GATE2009-54
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest ... of $L[M, N]$. $L[p, q]$ needs to be computed before $L[r, s]$ if either $p<r$ or $q < s$.
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest common ... major order of $L[M, N]$. $L[p, q]$ needs to be computed before $L[r, s]$ if either $p<r$ or $q < s$.
asked Apr 23, 2016 in Algorithms jothee 6.3k views
30 votes
3 answers
2
4.2k views
GATE2009-53
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the ... $\text{expr2} = \max\left(l\left(i-1, j-1\right), l\left(i,j\right)\right)$
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest ... $\text{expr2} = \max\left(l\left(i-1, j-1\right), l\left(i,j\right)\right)$
asked Sep 22, 2014 in Algorithms Kathleen 4.2k views
37 votes
7 answers
3
10.3k views
GATE2009-39
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 complexity of the quick sort? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
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 complexity of the quick sort? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
asked Sep 22, 2014 in Algorithms Kathleen 10.3k views
22 votes
3 answers
4
4.9k views
GATE2009-35
The running time of an algorithm is represented by the following recurrence relation: $T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$ Which one of the following represents the time complexity of the algorithm? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
The running time of an algorithm is represented by the following recurrence relation: $T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$ Which one of the following represents the time complexity of the algorithm? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
asked Sep 22, 2014 in Algorithms Kathleen 4.9k views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...