Topological Sort
Order tasks so every task comes after the ones it depends on, and detect when no such order exists. Kahn's algorithm and the DFS version, in JS and Python.
On this page
You are making pizza at home with friends. The toppings cannot go on until the dough, the sauce and the grated cheese are ready. The pizza cannot bake until the toppings are on and the oven is hot. You cannot eat until it has baked. Four people want a job right now. Which jobs can start, and what is a full order that never makes anyone wait on something unfinished?
Each rule is a one-way link: "dough must come before toppings". That makes this a directed graph, as in Graph Basics, with an arrow from each task to the task that needs it. An order of all the tasks where every arrow points forward is called a topological order. Finding one is a topological sort.
There is usually more than one valid order. Dough, sauce, cheese, oven, toppings, bake, eat works. So does oven, cheese, sauce, dough, toppings, bake, eat. What never works is a cycle: if toppings needed bake and bake needed toppings, neither could ever start. A topological order exists exactly when the directed graph has no cycle. Such a graph is called a DAG (directed acyclic graph).
The idea: start with what nothing blocks
For each task, count the arrows coming into it. That count is its in-degree: the number of tasks it is still waiting on. A task with in-degree 0 is ready right now.
- Put every ready task (in-degree 0) in a queue.
- Take a task from the queue and add it to the order.
- It is done, so remove its outgoing arrows: subtract 1 from the in-degree of each task after it. Any task that drops to 0 has just become ready. Add it to the queue.
- Repeat until the queue is empty.
This is Kahn's algorithm. It looks a lot like BFS, but a task joins the queue only when its last blocker is done, not the first time anything points at it.
count incoming arrows (in) for every taskready = tasks with in = 0while ready is not empty: take a task, append it to order for each task after it: in = in - 1, if 0: add to readyorder has every task? done : there is a cycle- ready queue0D1S2C3Oorder
1Count incoming arrows for each task. D, S, C and O have none: nothing blocks them, so they start in the ready queue.
- ready queue0S1C2Oorder0D
2Take D. Its arrow to T goes away, so T now waits on 2 tasks instead of 3.
- ready queue0C1Oorder0D1S
3Take S. T drops to 1. Still blocked by C.
- ready queue0O1Torder0D1S2C
4Take C. T drops to 0: every task it needed is done, so T joins the ready queue.
- ready queue0Torder0D1S2C3O
5Take O. B drops to 1. It still needs T.
- ready queue0Border0D1S2C3O4T
6Take T. B drops to 0 and becomes ready.
- ready queue0Eorder0D1S2C3O4T5B
7Take B. E drops to 0 and becomes ready.
- ready queueorder0D1S2C3O4T5B6E
8Take E. Its list of next tasks is empty. The queue is empty too.
- ready queueorder0D1S2C3O4T5B6E
9All 7 tasks placed: D, S, C, O, T, B, E. Every arrow points from a task earlier in the order to one later. 7 tasks taken once, 6 arrows removed once.
The code
Notice the last line. If the graph has a cycle, the tasks on it never reach in-degree 0, so they never enter the queue. The order comes out shorter than the task list, and that is how you detect the cycle.
// rules: list of [before, after] pairs.
function taskOrder(tasks, rules) {
const next = {};
const inDegree = {};
for (const t of tasks) { next[t] = []; inDegree[t] = 0; }
for (const [before, after] of rules) {
next[before].push(after);
inDegree[after]++;
}
const queue = tasks.filter((t) => inDegree[t] === 0);
const order = [];
let head = 0;
while (head < queue.length) {
const task = queue[head++];
order.push(task);
for (const after of next[task]) {
inDegree[after]--;
if (inDegree[after] === 0) queue.push(after); // last blocker gone
}
}
return order.length === tasks.length ? order : null; // null: cycle
}
taskOrder(
["dough", "sauce", "cheese", "oven", "toppings", "bake", "eat"],
[["dough", "toppings"], ["sauce", "toppings"], ["cheese", "toppings"],
["toppings", "bake"], ["oven", "bake"], ["bake", "eat"]]
); // ["dough", "sauce", "cheese", "oven", "toppings", "bake", "eat"]from collections import deque
# rules: list of (before, after) pairs.
def task_order(tasks, rules):
nxt = {t: [] for t in tasks}
in_degree = {t: 0 for t in tasks}
for before, after in rules:
nxt[before].append(after)
in_degree[after] += 1
queue = deque(t for t in tasks if in_degree[t] == 0)
order = []
while queue:
task = queue.popleft()
order.append(task)
for after in nxt[task]:
in_degree[after] -= 1
if in_degree[after] == 0:
queue.append(after) # last blocker gone
return order if len(order) == len(tasks) else None # None: cycle
task_order(
["dough", "sauce", "cheese", "oven", "toppings", "bake", "eat"],
[("dough", "toppings"), ("sauce", "toppings"), ("cheese", "toppings"),
("toppings", "bake"), ("oven", "bake"), ("bake", "eat")],
) # ['dough', 'sauce', 'cheese', 'oven', 'toppings', 'bake', 'eat']Counting in-degrees reads every rule once. Each task enters the queue once, and each arrow is removed once. The lists of next tasks hold E entries.
The DFS version
Depth-First Search gives a second way. A DFS call on a task does not return until it has finished every task reachable from it, which is every task that must come after it. So when a task finishes, everything that depends on it has already finished. Write tasks down in the order they finish, then reverse the list.
Cycle detection needs one extra state. A task is either unvisited, on the current path (its call has started but not returned), or finished. If DFS reaches a task that is on the current path, it has followed arrows in a circle, and there is no valid order.
function taskOrderDfs(tasks, rules) {
const next = {};
for (const t of tasks) next[t] = [];
for (const [before, after] of rules) next[before].push(after);
const state = {}; // undefined: unvisited, 1: on the path, 2: finished
const finished = [];
function visit(task) {
if (state[task] === 2) return true;
if (state[task] === 1) return false; // back on our own path: cycle
state[task] = 1;
for (const after of next[task]) {
if (!visit(after)) return false;
}
state[task] = 2;
finished.push(task); // everything after it is already finished
return true;
}
for (const t of tasks) {
if (!visit(t)) return null;
}
return finished.reverse();
}
// pizza tasks → ["oven", "cheese", "sauce", "dough", "toppings", "bake", "eat"]def task_order_dfs(tasks, rules):
nxt = {t: [] for t in tasks}
for before, after in rules:
nxt[before].append(after)
state = {} # missing: unvisited, 1: on the path, 2: finished
finished = []
def visit(task):
if state.get(task) == 2:
return True
if state.get(task) == 1:
return False # back on our own path: cycle
state[task] = 1
for after in nxt[task]:
if not visit(after):
return False
state[task] = 2
finished.append(task) # everything after it is already finished
return True
for t in tasks:
if not visit(t):
return None
return finished[::-1]
# pizza tasks → ['oven', 'cheese', 'sauce', 'dough', 'toppings', 'bake', 'eat']On the pizza tasks, DFS starts at dough and runs dough, toppings, bake, eat. Eat finishes first, then bake, toppings and dough. Sauce, cheese and oven each finish straight away. Reversed, that gives a different order from Kahn's, and an equally valid one. Both versions are O(V + E). Kahn's needs no recursion, so it is the safer choice on large inputs; the DFS version is handy when you are already writing a DFS.
Common mistakes
Check yourself
Using the pizza rules, which of these is not a valid order?
You run Kahn's algorithm on 6 tasks and the order comes out with only 4. What does that tell you?
Rules: A before B, A before C, B before D, C before D. What is D's in-degree at the start?
What to practise next
The next module asks harder questions about the same graphs. Union-Find answers "are these two connected?" while edges keep arriving, and Dijkstra's algorithm finds shortest paths when edges have weights.