Awesome q2a theme
0 votes

Consider the following graph:

The minimum size of queue required when performing BFS on above graph is ________.
(Take size of queue as by maximum number of elements at any time).


What will be the correct answer for the foolowing question?

in DS by (73 points) | 86 views
I think 4 should be the minimum (if you start from E, B, F, C or G).

You can do it with 3, if you start from A or D. But with a queue of size 4, it is guaranteed that you can perform BFS no matter which node you start from.
Answer provided by made easy is 4. But I think it should be 5.

Queue content:

=> C

=> B | E | G | D

=> E | G | D | A | F.    here 5 nodes are present at the same time.
Ooh good observation !
yes ,even i got 5 as the answer.

1 Answer

0 votes
I think this question do not make any sense, because reason is - I got size of Queue as 3 starting from A to D. Now as we all know bfs of any graph is not unique and whichever BFS u or me have found correctly then no matter that which vertex is taken as starting vertex because Question is JUST saying BFS so my BFS starting from A is also a BFS no matter what is starting vertex and i have done it using 3 size Queue so minimum requirement will be 3 .

So 3 will be correct answer . and by the way this Question does not make any sense.
by (5 points)
GATE2021 it is clearly said in the question "Take size of queue as by maximum number of elements at any time". So the question is correct and correct answer will be 5.
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
9,020 questions
3,138 answers
95,828 users