general doubt on breadth first search

Question

While doing BFS , at any time in queue suppose there are r vertices v1,v2,v3.....vr with v.d as the distance from the source.

Then according to me at any time in a queue,

v1.d=v2.d

or

v2.d=v1.d+1

But in cormen its written that v2.d<=v1.d+1

Can someone please explain?

Comments

I ALSO TRIED ALL POSSIBILITIES AS PER GIVEN   QUEUE  WHERE V2 IS NEXT TO V1

U SEEMS CORRECT UNTIL  ANY TWIST IN THE QUESTION U MISSED TO PUT HERE...........

---

its a general corollary given in cormen. It is a straight forward statement. U can check in cormen. Since BFS explores vertices level by level so it is quite logical that 

v1.d=v2.d

or

v2.d=v1.d+1.

 

---

YA IT IS GIVEN BUT PROOF ALSO GIVEN WHICH IS TOTALLY OUT OF REACH OF MIND IT MAY BE CORRECT

---

Yes completely out of reach. I wasted so many hours on dat.

Answer 1

Fig 1 is Graph G

Fig 2 is BFS done on graph G

Bold Colour Edges in fig 2 are BFS Tree edges.

At Right side, instances of Queue 'Q' is derived.

Observe at instance no. 4 ., distance from source 's' to 'w' & 'v' is 1 & 2 respectively.

similarly at instance no 7, distance from source 's' to 'x' & 'u' is 2 & 3.

Therefore, v2.d <= v1.d + 1

Comments

The result which u got is same as i got but i was thinking that less means it could be less by 1,2,3 and so on.. my mistake.

Thanks for the answer. Got it clear.