GATE 2024 CS (CS1) – Question 45
Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ 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$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) There are no forward-edges in $G$ with respect to the tree $T$
Explanation
$T$ is both a DFS tree and a BFS tree rooted at $v$ of a **directed** graph $G$. Check each edge type.
- **Forward edges cannot exist.** A forward edge $u\to w$ goes from $u$ to a proper descendant $w$ that is not its child, so $\text{depth}_T(w)\ge\text{depth}_T(u)+2$. In a BFS tree, depth equals shortest distance from $v$, but the edge $u\to w$ would give $d(w)\le d(u)+1$. Contradiction. So (C) is true.
- **Back edges can exist.** $G$: $v\to a$ and $a\to v$. $T=\{v\to a\}$ is both a DFS and a BFS tree, and $a\to v$ is a back edge. So (A) is false, and (D) is false too (the edge $a\to v$ is not in $T$).
- **Cross edges can exist.** $G$: $v\to a$, $v\to b$, $b\to a$. DFS visits $a$ first, then $b$, so $b\to a$ is a cross edge; $T=\{v\to a,v\to b\}$ is also the BFS tree. So (B) is false.
Only (C) is always true.
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2024 CS (CS1) Q60
- GATE 2024 CS (CS2) Q59
- GATE 2023 CS Q56
- GATE 2022 CS Q49
- GATE 2021 CS (CS1) Q27
- GATE 2021 CS (CS1) Q46
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →