GATE CS 2025 Set 2 — Question 29

Statement (A) is FALSE. DFS does not necessarily produce a shortest path tree; BFS does (for unweighted graphs). For example, in a triangle graph with vertices $s, a, b$, a DFS might go $s \to a \to b$, giving path length 2 to $b$, while the direct edge $(s,b)$ has length 1.Statement (B) is TRUE. In the DFS of an undirected graph, every edge is either a tree edge or a back edge. There are no forward edges (as distinct from back edges in undirected context) or cross edges. Thus, every non-tree edge is a back edge, which satisfies the condition of being a "forward/back edge".Statement (C) is TRUE. In a BFS tree, for any edge $(u, v)$ in $G$, the levels of $u$ and $v$ differ by at most 1. Since the distance in the BFS tree corresponds to the level, $|d(s, u) - d(s, v)| \le 1$.Statement (D) is TRUE. Both BFS and DFS can be used to traverse a graph and identify connected components by starting a traversal from an unvisited node until all nodes are visited.