GATE CSE 2024 Session 1 Q45: Edge types when a DFS tree is also a BFS tree

Algorithms
2 marks
MSQ
No negative marking

Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$ . Suppose $T$ is also a breadth first search (BFS) tree in $G$ , rooted at $v$ . Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: C (official GATE 2024 final answer key)

Concept used: In a BFS tree no non-tree edge can skip more than one level downward.

First step: A forward edge would jump at least two levels down, contradicting BFS distances; then look for small graphs with a back or cross edge.

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 2024 Session 1 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

PracticePractise Algorithms questions →Full paperAll GATE CSE 2024 Session 1 questions →

GATE CSE 2024 Session 1 Q45: Edge types when a DFS tree is also a BFS tree

Question

Full step-by-step solution

More Algorithms PYQs