GATE CS 2025 Set 2 | Question 29

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph \(G\) is/are TRUE?

Option A: A DFS tree of \(G\) is a Shortest Path tree of \(G\).
Option B: Every non-tree edge of \(G\) with respect to a DFS tree is a forward/back edge. (correct)
Option C: If \((u, v)\) is a non-tree edge of \(G\) with respect to a BFS tree, then the distances from the source vertex \(s\) to \(u\) and \(v\) in the BFS tree are within \(\pm 1\) of each other. (correct)
Option D: Both BFS and DFS can be used to find the connected components of \(G\). (correct)

Answer

(B), (C), (D)

(A) False. In a triangle on \(s, a, b\), DFS from \(s\) may go \(s \to a \to b\), placing \(b\) at depth 2 although the edge \(sb\) puts it at distance 1.
(B) True. If \(u\) is discovered before its neighbour \(v\), then \(v\) is discovered before \(u\) finishes, so \(v\) becomes a descendant of \(u\). Every non-tree edge therefore joins a vertex to one of its ancestors; undirected DFS has no cross edges.
(C) True. BFS depths are shortest distances from \(s\), and an edge \((u, v)\) gives \(d(v) \le d(u) + 1\) and \(d(u) \le d(v) + 1\).
(D) True. Restarting the search (BFS or DFS) from each unvisited vertex visits exactly one connected component per start.

Answer: B, C, D