Test Series

Question

consider a graph. Let S is starting point to traverse.

At any time instance, what will be the maximum length of the queue if we apply BFS for the above-undirected graph?( Marks: -0.66 )

1.    5
2.    2
3.   4
4.   3

I think answer should be Option(3) i.e. 4 elements

Procedure:

1. Start with Point S

2.Visit S and enqueue adjacent to S i.e.(.w,r)

w

r

3.Visit(dequeue) w and enqueue (x,t)

r

x

t

4.Visit(dequeue) r and enqueue (v)

x

t

v

5.Visit(dequeue) x and enqueue (u,y)

t

v

u

y

Further steps will reduce the length of the queue.

So maximum length of the queue at any instance is 4.

Please correct me if I am wrong.

Comments

ys 4 must be the answer.....wecan change the order.... wx or xw  ..