edited by
13,884 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

1 votes
1 votes

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.

1 votes
1 votes

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

 

0 votes
0 votes

Please refer CLRS 3rd Edition Chapter 22(Elementary graph algorithms) Lemma 22.3 and Corollary 22.4

Screenshot Attached

Answer:

Related questions

65 votes
65 votes
11 answers
2
Ishrat Jahan asked Nov 3, 2014
17,503 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