chapter

Directed Acyclic Graphs and Topological Ordering PYQs for GATE DA

Solve 1+ Directed Acyclic Graphs and Topological Ordering previous year questions for GATE DA with answers and detailed solutions. Free sample questions below

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

2024 PYQ

Level 3: Exam Standard

Consider the directed acyclic graph (DAG) below: P R Q S V U T Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG?

Free preview ends here

Login to view the complete previous-year questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Directed Acyclic Graphs and Topological Ordering PYQs for GATE DA

Solve 1+ Directed Acyclic Graphs and Topological Ordering previous year questions for GATE DA with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Directed Acyclic Graphs and Topological Ordering

Chapter Roadmap

Directed Acyclic Graphs & Topological Ordering

The Foundation

Directed Acyclic Graphs (DAGs) and real-world task scheduling intuition.

The Core Mechanism

Formal definition of Topological Ordering and why cycles make it impossible.

The Algorithms

Kahn's Algorithm (in-degree and queue) and DFS-based approach (post-order and stack).

Exam Mastery

Identifying multiple valid sorts, detecting hidden cycles, and complexity analysis.

Topic Hero: Topological Ordering of DAGs

Topic Hero

Topological Ordering of DAGs

Topological ordering is a way to line up the vertices of a directed acyclic graph so that every directed edge points forward.

Imagine getting dressed: you must put on your socks before your shoes. A topological sort gives you a valid sequence to complete all tasks without violating any prerequisites.

Directed Acyclic Graphs and Topological Ordering: Solved Questions with Step-by-Step Explanations (1 Problems)

Question 1 · Programming, Data Structures and Algorithms · 2024 MSQ

Consider the directed acyclic graph (DAG) below:

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

A.
P Q R S T U V
B.
P R Q V S U T
C.
P Q R S V U T
D.
P R Q S V T U

Correct Answer:

["B","D"]

Step-by-Step Solution

Insight: A topological sort is valid if and only if for every directed edge $u \to v$ , vertex $u$ appears before vertex $v$ in the linear ordering.

Exam route: Extract all directed edges from the graph diagram. Check each given option to see if it violates any of these precedence constraints. Eliminate options with violations.

Learning route:

Step 1: Identify the vertices and directed edges from the SVG diagram.

The edges are: $P \to Q$ , $R \to Q$ , $Q \to S$ , $Q \to V$ , $S \to U$ , and $V \to T$ .

Step 2: List the precedence constraints derived from these edges:

$P$ must appear before $Q$ .
$R$ must appear before $Q$ .
$Q$ must appear before $S$ and $V$ .
$S$ must appear before $U$ .
$V$ must appear before $T$ .

Step 3: Evaluate each option against these constraints.

Option A ("P Q R S T U V"): $Q$ appears before $R$ . This violates the constraint $R \to Q$ . Invalid.
Option B ("P R Q V S U T"): $P, R$ are before $Q$ ; $Q$ is before $V$ and $S$ ; $S$ is before $U$ ; $V$ is before $T$ . All constraints are satisfied. Valid.
Option C ("P Q R S V U T"): $Q$ appears before $R$ . This violates the constraint $R \to Q$ . Invalid.
Option D ("P R Q S V T U"): $P, R$ are before $Q$ ; $Q$ is before $S$ and $V$ ; $S$ is before $U$ ; $V$ is before $T$ . All constraints are satisfied. Valid.

Step 4: Conclude that options B and D are the valid topological orderings.

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Directed Acyclic Graphs and Topological Ordering PYQs for GATE DA

Chapter Roadmap: Directed Acyclic Graphs and Topological Ordering

Directed Acyclic Graphs & Topological Ordering

Topic Hero: Topological Ordering of DAGs

Topological Ordering of DAGs

Directed Acyclic Graphs and Topological Ordering: Solved Questions with Step-by-Step Explanations (1 Problems)

Step-by-Step Solution

More previous year questions (pyqs) in this unit