GATE CS 2025 Set 2 Q19 — Graph Traversals (BFS, DFS)

Let us analyze each statement for an undirected simple graph $G$:

• Statement A (False): DFS does not guarantee shortest paths. For example, in a triangle graph with vertices $A, B, C$, a DFS starting at $A$ might yield the path $A \to B \to C$. The distance to $C$ in this DFS tree is $2$, whereas the actual shortest path distance is $1$.
• Statement B (True): In a DFS traversal of an undirected graph, there are no cross edges. Every non-tree edge must connect an ancestor to a descendant in the DFS tree, which classifies it as a back edge (or forward/back edge).
• Statement C (True): In a BFS tree of an undirected graph, any edge $(u, v)$ in $G$ can only connect vertices at the same level or at adjacent levels. Thus, the distances from the source $s$ satisfy $|d(s, u) - d(s, v)| \le 1$.
• Statement D (True): Both BFS and DFS can traverse all reachable vertices from a starting node. By repeatedly launching either traversal from any unvisited vertex, we can easily identify and count all connected components of $G$.