MadeEasy Test Series: Programming & DS - Graphs

Question

Consider the following graph:

The minimum size of queue required when performing BFS on above graph is ________.
(Size of queue is represented by maximum number of element at any time).

Comments

then what max size?

---

According to me what  minimum means(what i think) is that our choice should satisfy the constraints which can appear as worst case also.If we talk about maximum then it could be greater then 4 as well, we can take maximum as equal to number of nodes but that's pointless don't you think?.

In this question the min both is 4 and it cannot be 3. Becasue 3 satisfies only by working from A.and max Could be greater then 4 and bounded by total number of nodes present.

Please tell where i am wrong if i am wrong.

---

see I nowhere found, the difference between max and min depth in bfs
though https://stackoverflow.com/questions/687731/breadth-first-vs-depth-first is a good read for it
but explanation of made easy not correct
@Sambit will be correct here
for E it will be 4
and they might be asking for optimal depth

Answer 1

Minimum size means the size of queue which is sufficient for all cases (i.e. no matter from where the BFS starts, the queue will never overflow). Also this size should be minimum over all the other sizes which are sufficient.

Now since node E has 4 neighbours, the min size required to complete BFS, if the starting node is E, is 4.

Hence 4 is the answer.

Answer 2

Start from c...Pushed C

Pop E and then we need to push B,E,D,G...then pop G and push A,F...

Hence answer must be..... 5

Comments

Minimimum size 3 is possible as in above comments below questions.Also size 5 is possible.If you process C and then B and so on.

4 is in between.And given answer is 4.But i am not convinced why so?

---

@ rahul sharma 5

how did you get  5...???

---

See my last comment below question

---

ohh i got it...burst case requirement is 5....

it must be 5...

Answer 3

Queues size always equals to   number of vertices.

Hence    queue size is  always  in this question = # of vertices  7 ( min Or max case ) .

 

Max size of stack   :- means  no pop operation will occurs   in dfs ( stack) ..     Hence   here  we start   vertices A  .  

Sequence is    A B C D G E F   max size of stack is  7 .

Min size of stack :- means choose a path where more number of operation done.    

Sequence for minimum :- F E C D G B A    HERE   after C  ,   path  c d g  push in stack   and after   delet  g and d  from stack   .  Now we at point C,  and now onwards we add   b and a in stack.....      Hence total minimum size is    5 .

Comments

BRO WHY U EXPLAINING WRONG?

in bfs we are using queue not statck

---

it should be 5