GATE CSE 2001 | Question: 2.14

Question

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?

• A. $d(r,u) < d(r,v)$
• B. $d(r,u) > d(r,v)$
• C. $d(r,u) \leq d(r,v)$
• D. None of the above

Comments

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

---

Is the answer same incase of Depth First traversala also?

---

Yes @Yashaswini Vanaja it will be same for DFS also. 

Answer 1

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.

Answer 2

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

 

Answer 3

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

Screenshot Attached