GATE CS 2024 (Forenoon) — Question 45

AlgorithmsGraph Traversals (BFS, DFS) & Single-Source Shortest PathsMSQ2 marksMedium

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 \)?
  1. A
    There are no back-edges in \( G \) with respect to the tree \( T \).
  2. B
    There are no cross-edges in \( G \) with respect to the tree \( T \).
  3. C
    There are no forward-edges in \( G \) with respect to the tree \( T \).
  4. D
    The only edges in \( G \) are the edges in \( T \).
Practise the full 2024-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Graph Traversals (BFS, DFS) & Single-Source Shortest PathsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group