The GATE Grind

GATE 2024 CS (CS1) – Question 45

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple select

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$?

  1. There are no back-edges in $G$ with respect to the tree $T$
  2. There are no cross-edges in $G$ with respect to the tree $T$
  3. There are no forward-edges in $G$ with respect to the tree $T$
  4. The only edges in $G$ are the edges in $T$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) There are no cross-edges in $G$ with respect to the tree $T$; (C) There are no forward-edges in $G$ with respect to the tree $T$

Explanation

A tree that is both DFS and BFS forbids forward edges (they would skip BFS levels) and cross edges. Back edges to an ancestor can still exist, so A and D are false.