As, BFS traverses level by level, so either v is at the same level (sibling) or v is at just the next level from u.

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?

- $d(r,u) < d(r,v)$
- $d(r,u) > d(r,v)$
- $d(r,u) \leq d(r,v)$
- None of the above

### 3 Comments

As, BFS traverses level by level, so either v is at the same level (sibling) or v is at just the next level from u.

@ Manu Thakur sir

v is at just the next level from u.

v can be more than 1 level away(towards leaf) from u also.

## 7 Answers

### 6 Comments

Plz chk this answer

First of BFS doesnot calculate according to shorest distance. After root we can take node any order. But if we take any parent first, it's children should be select first. So, u is first taken than doesnot mean u have shortest distance than v. But there is also a possibility that distance of (r,v) is less than distance of (r,u) . So, according to me d) will be answer.

Considering all given constraints :-

u is visited before q means 2-cases can only occur:-

Hence option C is Ans.### 7 Comments

First of BFS doesnot calculate according to shorest distance. After root we can take node any order. But if we take any parent first, it's children should be select first. So, u is first taken than doesnot mean u have shortest distance than v. But there is also a possibility that distance of (r,v) is less than distance of (r,u) . So, according to me d) will be answer.

Here we have 2 cases

**Case 1**: If (u,v) is an edge in the graph then

$d(r,v)=d(r,u)+1$ and hence $d(r,u) \lt d(r,v)$

**Case 2**: if (u,v) is not an edge, and u and v are children of same parent say

Consider the above tree structure as some part of a given graph where r is my source vertex from which I started my BFS algorithm.

Now, minimum cost to reach X would be $d(r,x)$

Minimum cost to reach U would be $d(r,u)=d(r,x)+1=d(r,v)$ and this is equal to minimum cost to reach v from r via x.

So here we have $d(r,u)=d(r,v)$

Combining cases 1 and 2 we get

$d(r,u) \leq d(r,v)$

**Option (C)**

Given that 'u' is visited before 'v' during the breadth-first traversal.

There exist two cases:

1) Either 'u' and 'v' lies in the same level and 'u' is visited before 'v'. Therefore, distance from 'r' to 'u' & 'v' is same. Hence the sign of **equality** in option (C).

2) Second case is, 'u' and 'v' doesn't lie in the same level i.e 'u' is at level 'x' and 'v' is at level 'x+c' which means 'u' is visited before 'v' as per the given condition. Hence the sign of** less than(<)** in option (C).

So, **option (C) is correct.**

Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G.

it creates confusion lets make it clear

**length of path=no. of edges in the path**

**cost of path = sum of all weights of edges in the path **

here it clearly talks about length so in BFS a node is visited before its children are visited

if u is visited before v it means

- either u comes become v
- or u and v are at same level

to measure there distance from a node r

d(r,u)<=d(r,v)

then only in BFS we will first visit u

so option C