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: (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.

Only (C) is always true.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →