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.

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$
- $0$
- $1$
- $2$

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

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

+7

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?

Isn't this an issue with this question?

+6

they forget to add 'Unweighted' word i think.i wasted lot of time thinking about this question how to solve

0

how will we think without knowing that edge weight is unity? Is it default weight of any graph?

IIT key was ?

IIT key was ?

+2

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 .

+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)

0

srestha why we are assuming 1 for all ?

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

0

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.

+15 votes

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

Source : https://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec03-graphs.pdf

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:-

- u and v are in the same level, or
- u is one level above v, or
- 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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,370 answers

198,506 comments

105,272 users