Topological sort
In one line
A topological sort lists the nodes of a directed acyclic graph so that every edge points forward, giving a valid order for tasks with dependencies, and it exists only if there is no cycle.
What it is
Given a directed graph where an edge a to b means a must happen before b, a topological order is a sequence of all nodes in which every edge goes from earlier to later. Getting dressed is the classic example: socks before shoes, shirt before jacket.
A topological order exists if and only if the graph is a DAG (directed acyclic graph). If tasks depend on each other in a cycle, no task in the cycle can go first. There can be many valid orders; any one is usually acceptable.
Two standard algorithms run in O(V + E). Kahn's algorithm repeatedly removes nodes with no remaining incoming edges (in-degree 0). The DFS method lists nodes in reverse order of when they finish.
Why interviewers ask
Course schedule, build order, alien dictionary, parallel task scheduling and many dependency questions reduce to topological sort. Interviewers check that you build the edges in the right direction, detect cycles, and can explain why the algorithm is correct.
How it works
- 1Build the graph: for each dependency 'a before b', add edge a to b and increase indegree[b] by 1.
- 2Kahn's algorithm: put every node with indegree 0 into a queue. These have no unmet prerequisites.
- 3Pop a node, append it to the order, and for each outgoing edge decrease the neighbour's indegree. When a neighbour hits 0, push it.
- 4When the queue empties, if the order contains all V nodes it is a valid topological order. If not, the leftover nodes are in or behind a cycle.
- 5DFS alternative: run DFS from every unvisited node; when a node finishes (all descendants done), append it. Reverse the list at the end. An edge to an in-progress node signals a cycle.
- 6Processing Kahn's queue in rounds gives the minimum number of stages when unlimited tasks can run in parallel.
Worked example · Four courses with prerequisites
- Courses 0 to 3. Course 0 must come before 1 and before 2; courses 1 and 2 must both come before 3. Edges: 0 to 1, 0 to 2, 1 to 3, 2 to 3.
- Indegrees: 0 has 0, 1 has 1, 2 has 1, 3 has 2. Queue starts as [0].
- Pop 0, order [0]. Decrease 1 to 0 and 2 to 0; push both. Queue [1, 2].
- Pop 1, order [0, 1]. Decrease 3 from 2 to 1. Queue [2].
- Pop 2, order [0, 1, 2]. Decrease 3 to 0; push it. Queue [3].
- Pop 3, order [0, 1, 2, 3]. All 4 nodes placed, so there is no cycle. [0, 2, 1, 3] would also be valid.
- If we add edge 3 to 0, every node has indegree at least 1, the queue starts empty, and the order has 0 nodes: a cycle is detected.
Picture it
It is like cooking a recipe with steps that depend on others: you can only start steps whose ingredients are ready. Each finished step may unlock new ones. If two steps each need the other done first, the recipe is impossible.
Reference code
from collections import deque
def topo_order(n, edges):
# edges: (a, b) means a must come before b
adj = [[] for _ in range(n)]
indeg = [0] * n
for a, b in edges:
adj[a].append(b)
indeg[b] += 1
q = deque(u for u in range(n) if indeg[u] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1 # one prerequisite of v is done
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else [] # [] means there is a cycleKahn's algorithm: start from nodes with no prerequisites, and release each node when its last prerequisite is done. Each node and edge is handled once, so it is O(V + E). Note that LeetCode's course schedule gives pairs [course, prerequisite], so the edge there is prerequisite to course.
Key patterns
Can all tasks finish?
When: Course schedule, detect circular dependencies
How: Run Kahn's algorithm and check whether the output length equals V.
Return an order
When: Course schedule II, build order, install order
How: Kahn's output or reversed DFS finish order.
Derive edges from comparisons
When: Alien dictionary
How: Compare adjacent words; the first differing letters give an edge. Watch for a longer word before its own prefix, which is invalid.
Stages and longest path in a DAG
When: Minimum semesters, earliest finish time, critical path
How: Process Kahn's queue in rounds, or do DP over the topological order: finish[v] = max(finish[u] + duration[v]) over edges u to v.
Smallest lexicographic order
When: Several valid orders and the smallest one is required
How: Replace the queue with a min-heap, giving O((V + E) log V).
Real-world use
Build systems
Make, Bazel and Gradle model targets and their dependencies as a DAG and build in topological order, running independent targets in parallel and refusing circular dependencies.
Workflow schedulers
Apache Airflow pipelines are literally called DAGs: each task runs only after its upstream tasks succeed, and Airflow rejects DAG definitions with cycles.
Spreadsheets
Excel and Google Sheets track which cells depend on which; after an edit they recalculate affected cells in dependency order and report a circular reference error when a cycle appears.
Infrastructure as code
Terraform builds a dependency graph of resources (network before subnet before server) and walks it in topological order, creating independent resources in parallel.
In a project
Your data team runs 60 nightly SQL jobs where some read tables produced by others. They currently run in a hand-maintained order that breaks whenever someone adds a job, and the whole run takes 5 hours sequentially.
- Parse each job's input and output tables to derive edges: a job that writes table T comes before every job that reads T.
- Run Kahn's algorithm in rounds: every job in a round has all inputs ready, so all jobs in a round run in parallel.
- If not every job is placed, report the jobs left over as a dependency cycle and fail fast before anything runs.
- Schedule each round on a worker pool, and on a job failure skip only its downstream jobs.
- Regenerate the order automatically whenever a job's SQL changes.
Impact: No more manual ordering mistakes, cycles are caught at commit time, and running each round in parallel cut the nightly window from 5 hours to about 1.5 hours (bounded by the longest dependency chain).
Trade-offs
Use it when
- Tasks, builds, courses or jobs have before-and-after dependencies
- You need to detect circular dependencies
- You want the parallel stages or the critical path of a DAG
Avoid it when
- The graph is undirected: topological order is not defined
- Cycles are expected and allowed (for example mutual recursion): find strongly connected components first and sort the condensed graph
- You only need a single shortest path in an unweighted graph: BFS is enough
Cost: Kahn's and the DFS version are both O(V + E) time and O(V) extra space. With a min-heap for lexicographic order: O((V + E) log V).
Common mistakes
- Reversing edge direction: for pair [course, prereq], the edge goes prereq to course.
- Forgetting to check that all nodes were output, so a cycle silently returns a partial order.
- In the DFS version, forgetting to reverse the finish order, or using a two-state visited set that cannot detect cycles.
- Starting Kahn's queue only from node 0 instead of from every node with indegree 0.
- In alien dictionary, missing the invalid case where a word appears before its own prefix, like abc before ab.
Interview questions
Quick revision
- Only DAGs have a topological order; a cycle makes it impossible.
- Kahn: queue all indegree-0 nodes, pop, decrement neighbours, push new zeros.
- Output shorter than V means a cycle.
- DFS method: append on finish, then reverse.
- O(V + E) time; min-heap for smallest lexicographic order.
- Rounds of Kahn = parallel stages; DP over the order = critical path.
- [course, prereq] means edge prereq to course.
Check yourself
1. Kahn's algorithm finishes and the output contains 6 of 8 nodes. What does that tell you?
2. Edges: A to B, A to C, B to D, C to D. Which is a valid topological order?
3. In the DFS approach, when is a node added to the result list (before reversing)?
4. What is the time complexity of Kahn's algorithm with a plain queue?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.