edited by
13,889 views
38 votes
38 votes

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?

  1. $d(r,u) < d(r,v)$
  2. $d(r,u) > d(r,v)$
  3. $d(r,u) \leq d(r,v)$
  4. None of the above
edited by

7 Answers

Best answer
48 votes
48 votes

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:

  1. Either $u$ is closer to $v$, or,
  2. If $u$ & $v$ are same distance from $r$, then our BFS algo chose to visit $u$ before $v$.
edited by
33 votes
33 votes

Considering all given constraints :-

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

Hence option C is Ans.
2 votes
2 votes

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)

 

1 votes
1 votes
ans is C.

here if the distances d(r,u)=d(r,v) then also path from r will not be updated because if the distance is shorter then only path is updated.
Answer:

Related questions

65 votes
65 votes
11 answers
2
Ishrat Jahan asked Nov 3, 2014
17,519 views
In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is$k$$k+1$$n-k-1$$n-k$
49 votes
49 votes
8 answers
3