Understanding CLRS BFT lemma

I was reading BFT from CLRS. This is the example given in the book:

(Figure:The operation of BFS on an undirected graph. Tree edges are shown shaded as they are produced by BFS. The value of $u.d$ appears within each vertex $u$. The queue $Q$ is shown at the beginning of each iteration. Vertex distances appear below vertices in the queue.)

Then it gives following lemma:

Suppose that during the execution of BFS on a graph $G=(V,E)$, the queue $Q$ contains the vertices $<v_1,v_2,...,v_r>$, where $v_1$ is the head of $Q$ and $v_r$ is the tail. Then, $v_r.d\leq v_1.d+1$ and $v_i.d\leq v_{i+1}.d$ for $I=1,2,...,r-1$.

I am ok with $v_i.d\leq v_{i+1}.d$ for $I=1,2,...,r-1$ as I can observe this in all queue instances above. But I am not able to understand how $v_r.d\leq v_1.d+1$ aligns with above, as $i<i+1$, but $r>1$. How that $+1$ is making whole difference?

• Which is it, BFT or BFS? – Raphael Jan 31 '17 at 18:13

Suppose you have a tree like

        a           <-- level = 0
/ | \
b  c  d        <-- level = 1
/
f                 <-- level = 2

v1, v2, v3
Q : b,  c,  d
1,  1,  1

v3.d <= v1.d + 1   i.e 1 <= (1+1)


Now, suppose head of Q (i.e b) is removed and its neighbors are inserted in Q

    v1, v2, v3
Q : c,  d,  f
1,  1,  2

v3.d <= v1.d + 1   i.e 2 <= (1+1)


This, v3.d <= v1.d + 1 can be also be seen as v3.d - v1.d <= 1 which means at any point of time distance between elements of queue will always be less than or equal 1. This can also be seen from the fact that during the execution of BFT only elements from 2 successive levels are present in queue. There cannot be case such that 2 elements A and B are present in queue with A at level x and B at level (x + 2).

• ohh so when $v_i,d \leq v_{i+1}.d$ is holding, both of them are at the same level and while $v_r.d\leq v_1.d+1$ is holding, $v_r$ is at deeper/higher level than $v_1$, Right? – anir Jan 31 '17 at 10:55
• @anir: Correct. Elements at head of queue have less than or equal distance from source compared to elements at tail. If x is some distance from source then queue can have following 3 patterns: [1] x, x, x, ..., x [2] x, x, x, x, ...x+1 [3] x, x, x, ..., x+1, x+1,...,x+1 – sameerkn Jan 31 '17 at 11:11