Ordering Dependencies (Topological Sort)
Order tasks so every dependency comes first, with Kahn's algorithm — and detect a cycle when no such order exists.
Examples
4 and 5 wait on nothing, so they go first; every other node follows once its prerequisites are placed. Other valid orders are also accepted.
1, 2 and 3 wait on each other in a cycle, so no order exists.
What is Topological Sort?
Given a Directed Acyclic Graph (DAG), a Topological Sort is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before vertex v.
It is the standard algorithm for resolving dependencies (e.g., compiling code, scheduling tasks, course prerequisites).
The Motivation: Course Schedule
You need to take N courses. Some courses have prerequisites.
- Physics II requires Physics I.
- Calc III requires Calc II requires Calc I.
Goal: Find a valid order to take ALL courses. If impossible (due to a cycle), tell us.
The Cycle Problem
What if you have a cycle?
- Course A requires Course B.
- Course B requires Course A.
You can never start! This is a Circular Dependency. A Topological Sort is ONLY possible if the graph has NO Cycles (DAG).
You do not need a separate pass to find out. The walkthrough below orders the graph and, if it cannot, reports the cycle on the way.
When to use Topological Sort?
Pattern Recognition Triggers:
- Dependencies: Keywords like "prerequisites", "build order", "depends on".
- Linear Ordering: You need to arrange items in a sequence respecting constraints.
- Directed Graph: The relationships are one-way.
The Intuition: Find the Start
To start, we must find a node that has NO prerequisites (Indegree = 0).
- Pick a node with
Indegree == 0. Add it to our sorted list. - "Remove" it from the graph.
- When removed, its neighbors' indegrees decrease.
- Repeat until all nodes are picked.
This is Kahn's Algorithm.
Interactive Walkthrough (Kahn's Algo)
ARROW u → v = u BEFORE v · NUMBER ABOVE A NODE = PREREQUISITES STILL UNMET · GREEN = PLACED, RED = STUCK ON A CYCLE
COUNT IN-DEGREES
placed
0/6
queued
0
Answer
—
queue (front first)
Empty
order
Nothing placed yet
Build the lists from 6 edges and count each node's prerequisites: in-degrees [2, 2, 1, 1, 0, 0]
Next
Queue every node with nothing to wait for: [4, 5]
edges
n
Legend & Complexity
The node just taken off the queue
In the queue: nothing left to wait for
Placed — its edges are crossed off
Never reached 0 — waiting on a cycle
Time
O(V + E)
Space
O(V + E)
Each arrow u → v means u must come before v, and the number above a node is its in-degree — how many of its prerequisites are still unmet. Watch it count down as edges are crossed off: a node joins the queue the moment it reaches 0.
Load the Cycle preset to see the other ending. Once 0 is placed, nodes 1, 2 and 3 are each waiting on another of the three, so none of them ever reaches 0 — the queue runs dry, and the code returns []. Kahn's algorithm detects the cycle without looking for it.
Dry Run Table
The figure's default: n = 6, edges 5>2, 5>0, 4>0, 4>1, 2>3, 3>1. In-degrees start as [2, 2, 1, 1, 0, 0] for nodes 0 to 5.
| # | Queue | Take | Cross off | In-degree changes | Order |
|---|---|---|---|---|---|
| 1 | [4, 5] |
4 | 4>0, 4>1 |
0: 2→1, 1: 2→1 | [4] |
| 2 | [5] |
5 | 5>2, 5>0 |
2: 1→0, 0: 1→0 — queue both | [4, 5] |
| 3 | [2, 0] |
2 | 2>3 |
3: 1→0 — queue it | [4, 5, 2] |
| 4 | [0, 3] |
0 | — | — | [4, 5, 2, 0] |
| 5 | [3] |
3 | 3>1 |
1: 1→0 — queue it | [4, 5, 2, 0, 3] |
| 6 | [1] |
1 | — | — | [4, 5, 2, 0, 3, 1] |
All 6 nodes are placed, so the order is valid. Other valid orders exist — [5, 4, 2, 3, 0, 1] is one — and any of them is a correct answer.
Solution Template (Kahn's)
Kahn's algorithm in all six languages — the lines light up as the figure above steps.
Ordering Dependencies (Topological Sort) Code
1var topologicalSort = function(n, edges) {2 const graph = Array.from({ length: n }, () => []);3 const indegree = new Array(n).fill(0);4 for (const [u, v] of edges) {5 graph[u].push(v);6 indegree[v]++;7 }89 const queue = [];10 for (let i = 0; i < n; i++) {11 if (indegree[i] === 0) queue.push(i);12 }13 const order = [];14 let head = 0;15 while (head < queue.length) {16 const u = queue[head++];17 order.push(u);18 for (const v of graph[u]) {19 indegree[v]--;20 if (indegree[v] === 0) queue.push(v);21 }22 }2324 return order.length === n ? order : [];25};
Edge Cases & Checks
Critical checks:
Cycle: if the order ends with fewer than
nnodes, some nodes never reached in-degree 0 — they are waiting on each other. Return[].Disconnected graph: fine. Every component's sources start in the queue together, and their orders interleave.
Many valid orders: a topological order is rarely unique. Any order in which every edge points forward is correct.
Self-loop:
u → uis a one-node cycle.uwaits on itself, never reaches 0, and the answer is[].Direction: here
[u, v]means u before v. LeetCode's Course Schedule writes[a, b]for "b before a" — build the edge the other way round.
Summary
Recap:
- Use Indegree to find starting points.
- Use BFS (Queue) to peel layers.
- If queue empties and graph still has nodes, there's a Cycle.