DSA Patterns Made Simple · Trees and Graphs
Topological Sort: Ordering Tasks With Dependencies
Courses with prerequisites, build steps, package installs: when tasks depend on other tasks, repeatedly take the ones with no remaining prerequisites. If you get stuck, there's a cycle.
The problem
Course Schedule: you must take 4 courses; course 1 needs course 0, course 2 needs 0, and course 3 needs both 1 and 2. In what order can you take them? And if course 0 also needed course 3, could you finish at all?
How to spot it
- Prerequisites, dependencies, "must happen before"
- "Find an order", "can all tasks be finished?", build order, package installation
- A directed graph where a cycle means "impossible"
The idea
This is Kahn's algorithm, and it's how you'd plan by hand:
- Count, for each task, how many prerequisites it still has (its in-degree).
- Put every task with zero prerequisites in a queue: you can do those now.
- Take one from the queue, add it to the order, and "tick it off" for every task that depended on it (decrease their counts). Any task whose count drops to zero joins the queue.
- If the order contains every task, that's a valid plan. If tasks are left over, they're stuck waiting on each other: there's a cycle.
The template
from collections import deque
graph = {t: [] for t in range(n)} # prerequisite -> tasks that need it
indegree = [0] * n
for task, prereq in edges:
graph[prereq].append(task)
indegree[task] += 1
queue = deque(t for t in range(n) if indegree[t] == 0)
order = []
while queue:
t = queue.popleft()
order.append(t)
for nxt in graph[t]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == n else [] # [] means there is a cycle
const graph = Array.from({ length: n }, () => []); // prerequisite -> tasks that need it
const indegree = new Array(n).fill(0);
for (const [task, prereq] of edges) {
graph[prereq].push(task);
indegree[task]++;
}
const queue = [];
for (let t = 0; t < n; t++) if (indegree[t] === 0) queue.push(t);
const order = [];
for (let i = 0; i < queue.length; i++) { // queue grows as we go
const t = queue[i];
order.push(t);
for (const nxt of graph[t]) if (--indegree[nxt] === 0) queue.push(nxt);
}
return order.length === n ? order : []; // [] means there is a cycle
Worked example
Plan the four courses, detect an impossible schedule, and order build steps by name.
from collections import deque
def course_order(n, prerequisites):
graph = {t: [] for t in range(n)}
indegree = [0] * n
for course, needs in prerequisites:
graph[needs].append(course)
indegree[course] += 1
queue = deque(t for t in range(n) if indegree[t] == 0)
order = []
while queue:
t = queue.popleft()
order.append(t)
for nxt in graph[t]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == n else []
def build_order(steps):
names = sorted(steps)
index = {name: i for i, name in enumerate(names)}
edges = [(index[step], index[dep]) for step, deps in steps.items() for dep in deps]
return [names[i] for i in course_order(len(names), edges)]
print("order:", course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))
print("with a cycle:", course_order(2, [[1, 0], [0, 1]]) or "impossible")
print("build:", " -> ".join(build_order({
"deploy": ["test", "build"],
"test": ["build"],
"build": ["install"],
"install": [],
})))
Output
order: [0, 1, 2, 3] with a cycle: impossible build: install -> build -> test -> deploy
function courseOrder(n, prerequisites) {
const graph = Array.from({ length: n }, () => []);
const indegree = new Array(n).fill(0);
for (const [course, needs] of prerequisites) {
graph[needs].push(course);
indegree[course]++;
}
const queue = [];
for (let t = 0; t < n; t++) if (indegree[t] === 0) queue.push(t);
const order = [];
for (let i = 0; i < queue.length; i++) {
const t = queue[i];
order.push(t);
for (const nxt of graph[t]) if (--indegree[nxt] === 0) queue.push(nxt);
}
return order.length === n ? order : [];
}
function buildOrder(steps) {
const names = Object.keys(steps).sort();
const index = Object.fromEntries(names.map((name, i) => [name, i]));
const edges = Object.entries(steps).flatMap(([step, deps]) => deps.map((dep) => [index[step], index[dep]]));
return courseOrder(names.length, edges).map((i) => names[i]);
}
const show = (v) => JSON.stringify(v).replaceAll(",", ", ");
console.log("order:", show(courseOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]])));
const cyclic = courseOrder(2, [[1, 0], [0, 1]]);
console.log("with a cycle:", cyclic.length ? show(cyclic) : "impossible");
console.log("build:", buildOrder({
deploy: ["test", "build"],
test: ["build"],
build: ["install"],
install: [],
}).join(" -> "));
Output
order: [0, 1, 2, 3] with a cycle: impossible build: install -> build -> test -> deploy
Common mistakes
- Reversing the edges.
[1, 0]usually means "1 needs 0", so the arrow goes 0 → 1. Get this wrong and the order comes out backwards. - Forgetting the cycle check. If
len(order) < n, some tasks never reached zero prerequisites. - Missing isolated tasks. Tasks with no edges at all still belong in the order; build the graph for all n tasks.
- Expecting one unique answer. Several orders can be valid; tests usually accept any of them.
Practice
- Course Schedule (medium)
Key points
- Count prerequisites (in-degree); start with tasks that have none.
- Taking a task "ticks off" its dependants; zero means ready.
- If not every task gets ordered, there's a cycle.
- O(V + E): every task and dependency is handled once.
Practice questions
How does Kahn's algorithm detect a cycle?
Answer
Tasks in a cycle always keep at least one unmet prerequisite (each waits on another in the cycle), so their in-degree never reaches zero and they never enter the queue. If the final order has fewer than n tasks, there's a cycle.
What does the edge [1, 0] mean in Course Schedule, and which way does the graph edge point?
Answer
Course 1 requires course 0. The graph edge points from the prerequisite to the course (0 → 1), and course 1's in-degree increases.
Open in the app to mark lessons complete, take notes and track your progress.