The GATE Grind

GATE 2021 CS (CS2) – Question 56

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

For the directed graph shown, which statements hold?

Diagram for GATE 2021 CS (CS2) question 56
  1. There is no topological order
  2. A DFS starting at S classifies three directed edges as back edges
  3. There is no strongly connected component
  4. For every pair u,v, there is a directed path from u to v

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) There is no topological order; (B) A DFS starting at S classifies three directed edges as back edges

Explanation

The drawing contains three directed cycles in separate strongly connected regions: the lower-left square, central upper square and lower-right square. DFS from S encounters a back edge closing each, giving three back edges. A directed cycle prevents a topological ordering. Strongly connected components do exist, and edges between regions are not all reversible, so the entire graph is not strongly connected. Select A,B.

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

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