The GATE Grind

GATE 2025 CS (CS2) – Question 29

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Multiple select

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

  1. A DFS tree of $G$ is a Shortest Path tree of $G$.
  2. Every non-tree edge of $G$ with respect to a DFS tree is a forward/back edge.
  3. 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.
  4. Both BFS and DFS can be used to find the connected components of $G$.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) Every non-tree edge of $G$ with respect to a DFS tree is a forward/back edge.; (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.; (D) Both BFS and DFS can be used to find the connected components of $G$.

Explanation

A DFS tree need not give shortest paths, so A is false. In undirected graphs DFS has no cross edges, so non-tree edges are back/forward edges. BFS non-tree edges join vertices whose levels differ by at most 1, and both traversals find connected components.