The Gateway to Computer Science Excellence
+29 votes

Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ be the resultant BFS tree. If $(u, v)$ is an edge of $G$ that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$?

  1. $-1$
  2. $0$
  3. $1$
  4. $2$
in Algorithms by Boss (30.8k points)
edited by | 5.4k views
Q. - > Why edge weight is considered as 1 ?

Ans. -> I graph edge weight is 1 then BFS could be used for finding single source shortest path. If edge weight is not assumed to be then all options are possible. Please correct me if i am wrong.
If nothing is mentioned then we always consider singular weight.

7 Answers

+44 votes
Best answer
$2$ is the answer.

$d(u) - d(v) = 0$ is possible when both $u$ and $v$ have an edge from $t$ and $t$ is in the shortest path from $s$ to $u$ or $v$.

$d(u) - d(v) = 1$ is possible when $v$ and $t$ are in the shortest path from $s$ to $u$ and both $t$ and $v$ are siblings- same distance from $s$ to both $t$ and $v$ causing $t-u$ edge to be in BFS tree and not $v-u$.

$d(u) - d(v) = -1$ is possible as explained above by interchanging $u$ and $v$.

$d(u) - d(v) = 2$ is not possible. This is because on BFS traversal we either visit $u$ first or $v$. Let's take $u$ first. Now, we put all neighbors of $u$ on queue. Since $v$ is a neighbour and $v$ is not visited before as assumed, $d(v)$ will become $d(u) + 1$. Similarly, for $v$ being visited first.
by Veteran (431k points)
edited by
edge weight is not defined. There is never a place where they say that edge weight is unity.

Isn't this an issue with this question?
I suppose that is a fair assumption given what all others we assume :)
they forget to add 'Unweighted' word i think.i wasted lot of time thinking about this question how to solve
how will we think without knowing that edge weight is unity? Is it default weight of any graph?
IIT key was ?
bfs works when all the edge weights are equal to find the shortest path not only when 1 .they should be equal thats it so if we take some value 2 then even D is possible they should have mentioned in the question but looking at the given options we should come to a consclusion that edge weights are assumed to be 1 .

Extract from coremen

$\delta (u,v)$ indicates the shortest path from vertex u to v.

I'm unable to understand the solution here.. Is the BFS tree that's constructed not for the entire graph ? Because, if it is for the entire graph, then all the edges must be covered, right ? Is there anything here related to acyclicness of a tress that I'm missing ?
+34 votes

(B)Take distance from S

d(U) =1 from S

d(V)=1 from S

So, d(U) - d(V) =0 , d(X) is one shortest distance of the graph

and BFS traversal will not take edge UV

(C) Now for assuming d(U) and d(V) has a distance 1, we similarly calculate the distance from S(in next figure)

(A)In previous figure change the position of U and V, so get

d(U)-d(V) = -1

(D) but 2 not possible as there is a direct edge from U to V always, So, no graph possible with min distance 2. The max distance could be 1 

So, ans is (D)

by Veteran (119k points)
edited by

srestha why we are assuming 1 for all ?

for any type of graph whose weights are distinct it is not satisfying the condition 


explaining option D bit more

In above diagram d(u) = 3 and d(v) = 1 hence difference is 2 , but is this diagram valid

No , because if V and U were connected then in DFS of graph U will come at level 2 and not at level 3 . and then distance of U = 2 and d(v) =1 hence difference will be 1 only.

Hence option d is not possible.

+23 votes

By Option Elimination:-

Here (2,3) or (3,2)and (3,4) or (4,3) pairs eligible for (u,v) pair as per question bcz these edges are not part of BFS Tree.

lets take (2,3) here d(2)-d(3)=1-1=0 So Option B is feasible 

now (3,4) here d(3)-d(4)=1-2=-1 , So Option A is feasible

now (4,3) here d(4)-d(3)=2-1=1 So Option C is feasible

Hence Option D is Ans.

by Boss (23.9k points)
@ Rajesh Pradhan , very good solution
+15 votes

By having known this property, answer is straight away 2 i.e. option D.

Source :

by Boss (29.1k points)
+1 vote
answer is d
by Active (1.4k points)
0 votes
option d... thanku arjun sir
by Active (5k points)
edited by
both u and v can be child nodes of the same parent rt?
0 votes

BFS tree is constructed level by level. (We cover the whole level's breadth at one go)

If $u,v$ is an edge in the graph, then in BFS tree, either:-

  1. u and v are in the same level, or
  2. u is one level above v, or
  3. v is one level above u

In an unweighted graph(fair assumption), the distance between two nodes = number of edges between them. Clearly, the edges between u and v can't be 2.

Option D


Page 790, Kenneth H Rosen.

ago by Loyal (6.8k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,370 answers
105,272 users