edited by
18,016 views
51 votes
51 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$
edited by

10 Answers

0 votes
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.

0 votes
0 votes
In an undirected graph if (u, v) be the edge then (u, v) also the edge. So shortest path that can be obtained by the (u, v) of (u, v).
Then the difference between the d(u) and d(v) is not more than '1'.
In the option 'D' the difference is given as '2' it is not possible in the undirected graph.
Answer:

Related questions

34 votes
34 votes
4 answers
1
go_editor asked Sep 26, 2014
12,106 views
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjac...
49 votes
49 votes
8 answers
2