GATE CS 2025 (Afternoon) — Question 29

AlgorithmsGraph Traversals (BFS, DFS) & Single-Source Shortest PathsMSQ1 markMedium

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
    A DFS tree of \( G \) is a Shortest Path tree of \( G \).
  2. B
    Every non-tree edge of \( G \) with respect to a DFS tree is a forward/back edge.
  3. 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.
  4. D
    Both BFS and DFS can be used to find the connected components of \( G \).
Practise the full 2025-AN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Graph Traversals (BFS, DFS) & Single-Source Shortest PathsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group