GATE CS 2021 (Afternoon) — Question 56

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

Consider the following directed graph:
Question image
Which of the following is/are correct about the graph?
  1. A
    The graph does not have a topological order.
  2. B
    A depth-first traversal starting at vertex \(S\) classifies three directed edges as back edges.
  3. C
    The graph does not have a strongly connected component.
  4. D
    For each pair of vertices \(u\) and \(v\), there is a directed path from \(u\) to \(v\).
Practise the full 2021-AN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAFree All-India Mock — every SundayA full GATE CS paper, exactly 180 minutes, ranked across India with your GATE score.
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