DSA & Algorithms
Part 16 of 21 · DSA Interview PatternsGraphs — Topological Sort & DAGs — Kahn, DFS Finish Times & Cycles
Kahn and DFS topo sort on DAGs; detect cycles and order dependencies.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Dependencies need an order, and the graph is directed
Prefer
Topological sort
Kahn peels sources. DFS records finish times. If you cannot order every node, the graph is not a DAG.
- A node enters the queue when its last prerequisite is removed.
- Lexicographically smallest order swaps the queue for a priority queue.
- Undirected graphs do not have a topological order.
Alternative
DFS and hope the visit order is the build order
Visit order is not finish order. The reverse of finish times is the topo order.
- Pointing prerequisite edges backward.
- Returning a partial order and missing the cycle.
- Applying the algorithm to an undirected graph.
Peel sources, or finish and reverse
Two correct algorithms. Kahn is easier to explain at a whiteboard.
- 1
Queue every indegree-zero node
Those have no remaining prerequisites. - 2
Delete outgoing edges
A neighbor that hits zero joins the queue. - 3
Stop
n nodes means a valid order. Fewer means a cycle.
Overview
Kahn and DFS topo sort on DAGs; detect cycles and order dependencies.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use on DAGs when you need a valid order of dependencies (build order, course schedule).
Recognition cues
- course schedule / prerequisites
- alien dictionary
- build order
- detect cycle in directed graph
Mental model
Decisions
- 1
Step 1 Count the indegree of every node
- nextStep 2 Queue every node with indegree 0
- 2
Step 2 Queue every node with indegree 0
- nextStep 3 Queue empty?
- ?
Step 3 Queue empty?
- noStep 4 Pop u, append to order
- yesStep 7 order holds all V nodes?
- 4
Step 4 Pop u, append to order
- nextStep 5 For each edge u to v, indegree v -= 1
- 5
Step 5 For each edge u to v, indegree v -= 1
- nextStep 6 Push v when its indegree hits 0
- 6
Step 6 Push v when its indegree hits 0
- nextStep 3 Queue empty?
- ?
Step 7 order holds all V nodes?
- yesStep 8 Valid topological order
- noFailure path - cycle, no valid order exists
- 8
Step 8 Valid topological order
- 9
Failure path - cycle, no valid order exists
Lesson map
Graphs — Topological Sort & DAGs — Kahn, DFS Finish Times & Cycles
Kahn and DFS topo sort on DAGs; detect cycles and order dependencies.
Architecture. Step 1 Count the indegree of every node Ready. Step 2 Queue every node with indegree 0 Ready. Step 3 Queue empty? Ready. Step 4 Pop u, append to order Ready. Step 5 For each edge u to v, indegree v -= 1 Ready. Step 6 Push v when its indegree hits 0 Ready. Step 7 order holds all V nodes? Ready. Step 8 Valid topological order Ready. Failure path - cycle, no valid order exists Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB I["Step 1 Count the indegree of every node Ready"] Q["Step 2 Queue every node with indegree 0 Ready"] E["Step 3 Queue empty? Ready"] P["Step 4 Pop u, append to order Ready"] R["Step 5 For each edge u to v, indegree v -= 1 Ready"] Z["Step 6 Push v when its indegree hits 0 Ready"] C["Step 7 order holds all V nodes? Ready"] OK["Step 8 Valid topological order Ready"] CY["Failure path - cycle, no valid order exists Ready"] I -->|continues| Q Q -->|continues| E E -->|no| P P -->|continues| R R -->|continues| Z Z -->|continues| E E -->|yes| C C -->|yes| OK C -->|no| CY
Flow
- 1
1. DFS from each node
- next2. Record the finish time
- 2
2. Record the finish time
- next3. Reverse finish order is topo
- 3
3. Reverse finish order is topo
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Kahn/DFS topo: O(V+E) time, O(V+E) space.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Course Schedule
- Course Schedule II
- Alien Dictionary
- Sequence Reconstruction
- Sort Items by Groups Respecting Dependencies
- Minimum Height Trees
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Kahn idea?
Answer
Repeatedly take indegree-zero nodes; if stuck, cycle.
DFS topo?
Answer
Push on finish; reverse postorder.
Cycle detection?
Answer
order length < n, or DFS hit gray node.
Lex smallest order?
Answer
Priority queue instead of FIFO among zero-indegree.
Alien dictionary?
Answer
Compare adjacent words at the first differing letter and add that edge once; a longer word before its own prefix (abc before ab) is invalid; then topo sort, and a cycle means invalid.
Why DAG only?
Answer
Cycles have no valid total order of dependencies.