LESSON 21 · PATTERN GUIDE

Topological Sort / DAG

Order directed acyclic graph nodes so every prerequisite appears before the work that depends on it.

FIRST, LEARN THE PATTERNKahn's algorithm repeatedly removes nodes with indegree zero. DFS can also order nodes by reverse finishing time.

The task has prerequisites, dependencies, course ordering, or asks whether a directed graph has a cycle.

How to approach it

Count incoming edges, queue zero-indegree nodes, and decrement neighbors. If fewer than all nodes are processed, a cycle exists.

Watch out for

A topological order exists only for a DAG and may not be unique.

A CLOSER EXPLANATION

A prerequisite edge points from required work to dependent work. Indegree counts how many prerequisites remain. Kahn's algorithm only schedules tasks with indegree zero, then releases their dependents; if tasks remain but none can start, there is a cycle.

NOW YOU TRY

Practice question

Give one valid order for tasks A, B, C, D with dependencies A→C, B→C, C→D.

EXAMPLEA and B must precede C; C must precede D.Give your answer before revealing the explanation.

Show a hint

Start with any task that has no prerequisites.

Show an answer

A, B, C, D (B, A, C, D is also valid).

CONNECT IT TO REAL LIFE

Topological Sort / DAG at work

A release has tasks: compile before test, test before package, and compile before documentation. Give a valid order that respects these dependencies.

Show one possible approach

Compile, then test and documentation in either order, then package. A topological ordering places each prerequisite before its dependents.

Practice next

Use these problem IDs to find additional practice for this pattern:

207210802146212032115