Register

GO Classes DPP | GATE CS, DA | Algorithms | BFS Tree

137 views
2 2 votes

Let $T$ be a breadth-first search tree of a undirected graph. Let $(x, y)$ be an edge of $G$ that is not an edge of $T$, then one of $x$ or $y$ is an ancestor of the other.

  1. True
     
  2. False

1 Answer

2 2 votes

Consider a BFS starting from source $s$.

Suppose,

$s$ has two children: $x$ and $y$ and there is also an edge: $(x,y)$

The BFS tree contains $(s,x)$ and $(s,y)$.

Both $x$ and $y$ lie at the same BFS level:

$d(s,x)=d(s,y)=1$

The edge $(x,y)$ is an edge of the original graph but is not a BFS-tree edge.

Also, neither $x$ nor $y$ is an ancestor of the other.

Therefore, a non-tree edge in BFS does not necessarily connect an ancestor and a descendant.

In fact, for an undirected graph, an edge can connect vertices on:

  • the same BFS level, or
     
  • two consecutive BFS levels.
     

Thus the statement is false.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

2 2 votes
1 1 answer
134
134 views
GO Classes asked Aug 14
134 views
GO Classes DPP | GATE CS, DA | Algorithms | BFS Maximum Space
BFS is performed from the root of a binary tree containing $n$ vertices.For which type of binary tree can BFS require $\Theta(n)$ extra space in the worst case?A complete...
2 2 votes
1 1 answer
238
238 views
GO Classes asked Aug 14
238 views
GO Classes DPP | GATE CS, DA | Algorithms | BFS Graph
Suppose BFS is run on a cycle graph $C_n$. For which values of $n$ will no coloring conflict occur?All $n$ Odd $n$ Even $n$ Only prime $n$
2 2 votes
1 1 answer
104
104 views
GO Classes asked Aug 14
104 views
GO Classes DPP | GATE CS, DA | Algorithms | BFS in Di-graph
Breadth-first search (BFS) will visit every vertex in a directed graph, in nondecreasing order from the source.True False
2 2 votes
1 1 answer
125
125 views
GO Classes asked Aug 14
125 views
GO Classes DPP | GATE CS, DA | Algorithms | BFS Queue
Consider the standard BFS algorithm, except for one modification:A vertex is marked as visited only when it is removed from the queue, instead of when it is first inserte...