The GATE Grind

GATE 2014 CS (CS1) – Question 23

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Multiple choice

For the directed graph shown, which statement is TRUE?

Diagram for GATE 2014 CS (CS1) question 23
  1. The graph has no topological ordering.
  2. PQRS and SRQP are both topological orderings.
  3. PSRQ and SPRQ are both topological orderings.
  4. PSRQ is the only topological ordering.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) PSRQ and SPRQ are both topological orderings.

Explanation

The edges require both P and S before R, and R before Q; P and S may appear in either order. Consequently PSRQ and SPRQ both respect every edge, giving **C**. An ordering with Q before R violates R→Q.