GATE CS 2025 Set 2 Q.29: Graph Traversals, Topological Sort and Connectivity

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

A DFS tree of $G$ is a Shortest Path tree of $G$ .

Every non-tree edge of $G$ with respect to a DFS tree is a forward/back edge.

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.

Both BFS and DFS can be used to find the connected components of $G$ .

Official answer and solution

Official answer: B, C and D
From: Official GATE 2025 answer key

Solution

Verify standard properties of BFS and DFS trees on undirected graphs.

(A) is FALSE: A BFS tree is a shortest-path tree for an unweighted graph, whereas a DFS tree is generally not.
(B) is TRUE: In a DFS of an undirected graph, there are no cross edges; every non-tree edge connects a vertex to one of its ancestors/descendants in the DFS tree (a back/forward edge).
(C) is TRUE: In a BFS of an undirected graph, any non-tree edge $(u, v)$ connects vertices in either the same BFS level or adjacent BFS levels, so $|d(s, u) - d(s, v)| \le 1$ .
(D) is TRUE: Both BFS and DFS visit all and only the vertices reachable from the starting vertex, so both can identify the connected components of $G$ .

Final answer

Options (B), (C), (D)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 29 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source