Skip to content
GATEiit

GATE CSE 2025 Session 2 Q29: True statements about BFS and DFS trees of an undirected graph

Question

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

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: B, C, D (official GATE 2025 final answer key)

Concept used: Edge classification: undirected DFS has no cross edges; BFS levels of adjacent vertices differ by at most 1.

First step: Test (A) on a triangle: DFS from one vertex reaches the third vertex at depth 2, though it is a neighbour.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 2 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2025 Session 2 questions →