Pattern 14: Topological Sort

Deep Dive: Kahn's Algorithm Step by Step

Course Schedule: 6 courses, prereqs: [[1,0],[2,0],[3,1],[3,2],[4,3],[5,3]]

Graph: 0 -> 1 -> 3 -> 4
       0 -> 2 -> 3 -> 5

In-degrees: 0:0  1:1  2:1  3:2  4:1  5:1

Queue = [0]       (only node with in-degree 0)
Pop 0: order=[0], decrement 1->0, 2->0. Queue=[1,2]
Pop 1: order=[0,1], decrement 3->1. Queue=[2]
Pop 2: order=[0,1,2], decrement 3->0. Queue=[3]
Pop 3: order=[0,1,2,3], decrement 4->0, 5->0. Queue=[4,5]
Pop 4: order=[0,1,2,3,4]. Queue=[5]
Pop 5: order=[0,1,2,3,4,5]. Queue=[]

Processed 6 == total nodes -> NO CYCLE. Valid order.

Cycle detection: If processed count < total nodes, some nodes never reached in-degree 0. Those nodes are in a cycle.

---

Signal: "Prerequisites", "dependency ordering", "course schedule", DAG ordering Template: topological_sort() in templates.py

When to Use

• "Can I finish all courses given prerequisites?"
• "Order tasks respecting dependencies"
• "Alien dictionary" (derive ordering from sorted words)
• Any DAG ordering problem

Two Approaches

Kahn's (BFS): Compute in-degrees -> process 0-degree nodes -> decrement neighbors
DFS: Post-order DFS -> reverse the result

Cycle detection: if processed count < total nodes -> cycle exists

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Course Schedule	Phase 1.9	20 min	[ ]
Course Schedule II	Phase 4.4	20 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Order tasks / courses / build steps that have prerequisites" — the explicit "before X you must do Y" is the strongest signal.
• "Can the schedule be completed?" — equivalent to "is the prerequisite graph a DAG?" — Kahn's tells you both the order and whether a cycle exists.
• "Derive an alphabet / ordering from a list of sorted items" (Alien Dictionary) — pairwise constraints form a DAG; topo-sort it.
• "Parallel job scheduling — minimum number of rounds" — layered topo-sort (BFS over successive in-degree-zero frontiers).

Anti-signals (looks like this pattern, isn't)

• "Shortest path in a DAG" — topo-sort is one phase, but the answer also needs an edge-relaxation pass; topo-sort alone isn't the algorithm.
• "Cycle detection in an undirected graph" — Union-Find or DFS with a parent argument; topo-sort is for directed graphs.
• "Order events that have NO inter-dependencies" — just sort by the relevant key (time, priority); no graph needed.