2
$\begingroup$

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

enter image description here (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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Which is it, BFT or BFS? $\endgroup$
    – Raphael ♦
    Jan 31, 2017 at 18:13

1 Answer 1

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – RajS
    Jan 31, 2017 at 10:55
  • $\begingroup$ @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 $\endgroup$
    – sameerkn
    Jan 31, 2017 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.