in Algorithms edited by
8,707 views
29 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
in Algorithms edited by
8.7k views

3 Comments

(C) is the correct option!

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.
11
Option A is wrong in Gate Overflow book, it is $\leq$ instead of $<$ @Arjun
0

 sir

v is at just the next level from u.

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

0

Subscribe to GO Classes for GATE CSE 2022

7 Answers

43 votes
 
Best answer

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

6 Comments

does BFS always take the shortest path to every node?
1
@Arjun Sir

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.
3
@srestha, if we choose a node $x$  to visit in BFS then children of this node will not be visited until all the siblings of this node(which are at the same distance from root ) will be explored.  henece if $u$ is visited first then only two cases are possible , either $u$ is nearest to root or $u$ is at the same distance as $v$ is.
7
sir can you elaborate  the proper meaning of option c,
0
r

/          \

v           u   consider the case when v is present as left child.

if distance is same it doesn't guarantee that u will be visited first , so it's guaranteed that u will be visited first of v if distance(u) is less than distance(v) so i think option A is correct .

correct me if i'm wrong!
1
The keyword :Unweighted graph.

So each edge individually can be considered of same length,say 1.the distance from ‘r’ to ‘u’ or ‘v’ is in terms of number of edges, not the length of edges.
0
30 votes

Considering all given constraints :-

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

Hence option C is Ans.

7 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.
1
@shreshta as question is on BFS and we know that bfs works on unweighted graph..what you are saying is that vertex v can also have small distance but its not possible if distance would have been small than it would have been more closer to root..so according to bfs as its level order we need to go by that theory...vertex v can only have same distance as u or greater than v..in these two cases only vertex u can be visited before u..!
1
edited by

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

1
SUPERB EXPLANATION.
0

@Krishna Madhav I also have the same doubt answer should be D. Please someone clarify this.

1
It is written graph in unweighted so there is no point of this type of exapmle
2
Short and accurate. Nice technique :)
0
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 vote
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.

2 Comments

In BFS can't we visit any adjacent vertex  of vertex r( in any order.) ..what is the concept of min distance here...?Please explain
3
u is visted before v.  therefore d[u] < d[v]

but u and v can be on same level.  therefore d[u] = d[v]

therefore d[u] <= d[v]
1
1 vote

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 vote

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

 

by
0 votes

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

Screenshot Attached

Answer:

Related questions