The GATE Grind

GATE 2024 DA – Question 51

Programming, Data Structures and Algorithms · Graph theory and basic graph algorithms · 2 marks · Multiple select

Consider the directed acyclic graph (DAG) below:

[Figure: a DAG with the edges P → Q, R → Q, Q → S, Q → V, S → U and V → T.]

Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG?

Diagram for GATE 2024 DA question 51
  1. P Q R S T U V
  2. P R Q V S U T
  3. P Q R S V U T
  4. P R Q S V T U

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) P R Q V S U T; (D) P R Q S V T U

Explanation

In a topological order, every vertex must come after all vertices with an edge into it: Q after P and R, S and V after Q, U after S and T after V. In A and C, Q comes before R, which breaks the edge R → Q. In B (P R Q V S U T) and D (P R Q S V T U) all the conditions hold.