Consider an undirected, unweighted graph $G$. Let a breadth-first traversal of $G$ be done starting from a node $r$. Let $d(r,u)$ and $d(r,v)$ be the lengths of the shortest paths from $r$ to $u$ and $v$ respectively in $G$. If $u$ is visited before $v$ during the breadth-first traversal, which of the following statements is correct?
Answer is $(C)$.
BFS is used to count shortest path from source (If all path costs are $1$)
Now, if $u$ is visited before $v$ it means $2$ things:
Considering all given constraints :-
u is visited before q means 2-cases can only occur:-
But still there are chances that even if the vertex v being traversed later has lesser distance than u.
Then I guess it should be not related as per option C and answer should be D.
Please refer CLRS 3rd Edition Chapter 22(Elementary graph algorithms) Lemma 22.3 and Corollary 22.4
@Arjun sir, i haven't got my consignment. the ...
Nice to see your plenty ...
For those who knows only about ...