A build pipeline has to install dependencies before generating code, generate code before compiling, and compile before testing. A university won’t let you take Algorithms before Data Structures. A spreadsheet must recalculate a cell only after every cell it references. Each of these is a directed graph where an edge means “this must happen before that”, and the question is the same: in what order can you do everything so that no step runs before its prerequisites?
That order is a topological sort. It exists if and only if the graph has no directed cycle (a directed acyclic graph, or DAG). If A needs B and B needs A, no order works. Interview problems test both halves: produce an order, and detect when none exists.
Get the edge direction right first
Before any algorithm, decide what an edge means and stick to it. Problems usually phrase dependencies as “X needs Y” or as pairs like [course, prerequisite]. For sorting, the natural edge points from the prerequisite to the dependent, Y → X, because “Y comes before X” is what the output order expresses.
Reversing the edges doesn’t make the algorithm fail. It produces a perfectly valid topological order of the reversed graph, which is your answer backwards, and every test that has a dependency fails. Write the direction as a comment next to the line that adds edges.
Kahn’s algorithm: take whatever is ready
Kahn’s algorithm (published by A. B. Kahn in 1962) thinks about the problem the way a person running a build would. A task is ready when all of its prerequisites are done. Keep a count of unmet prerequisites for every task, called its in-degree. Start with every task whose count is zero. Each time you complete one, decrement the count of everything that depended on it; anything that drops to zero becomes ready.
Here’s a small project with eight tasks. docs has no dependencies and nothing depends on it.
from collections import deque
# "X needs Y" pairs: Y must run before X
needs = [
("codegen", "install"),
("compile", "codegen"),
("lint", "install"),
("test", "compile"),
("package", "compile"),
("package", "lint"),
("deploy", "package"),
("deploy", "test"),
]
tasks = ["install", "codegen", "compile", "lint", "test", "package", "deploy", "docs"]
def kahn(tasks, needs):
graph = {t: [] for t in tasks}
indegree = {t: 0 for t in tasks} # every task, including ones with no edges
for task, prereq in needs:
graph[prereq].append(task) # edge points from prerequisite to dependent
indegree[task] += 1
queue = deque(t for t in tasks if indegree[t] == 0)
order = []
while queue:
t = queue.popleft()
order.append(t)
for nxt in graph[t]:
indegree[nxt] -= 1 # one fewer unmet prerequisite
if indegree[nxt] == 0:
queue.append(nxt)
if len(order) < len(tasks):
stuck = [t for t in tasks if indegree[t] > 0]
raise ValueError(f"cycle: could not schedule {stuck}")
return order
print(kahn(tasks, needs))['install', 'docs', 'codegen', 'lint', 'compile', 'test', 'package', 'deploy']Walk through it. Initially only install and docs have in-degree zero. Taking install drops codegen and lint to zero. Taking codegen frees compile. lint reduces package from 2 to 1, not enough yet. compile frees test and brings package to zero. Both test and package feed deploy, which becomes ready only after the second of them is done.
Every node is enqueued once and every edge is examined once, so the algorithm is O(V + E) time and O(V + E) space for the adjacency lists and counts.
How Kahn’s algorithm reports a cycle
If the graph has a cycle, the tasks in it can never reach in-degree zero: each is waiting on another member of the cycle. The queue empties early and order comes up short. Add the dependency “install needs test”, which closes the loop install → codegen → compile → test → install:
ValueError: cycle: could not schedule ['install', 'codegen', 'compile', 'lint', 'test', 'package', 'deploy']Only docs was scheduled. Notice that the stuck list is bigger than the cycle: lint, package and deploy aren’t part of the loop, but they’re downstream of it, so they’re stuck too. Kahn’s algorithm tells you that there’s a cycle and which tasks are blocked. To name the exact cycle, run a depth-first search with three node states, as the DFS cycle detection note does, which prints the loop itself.
The task that disappears
A tempting shortcut builds the graph only from the edge list, creating nodes as they appear in pairs. It looks equivalent. It isn’t:
built from edges only: ['install', 'codegen', 'lint', 'compile', 'test', 'package', 'deploy'] 7 of 8docs never appears in any dependency pair, so it never makes it into the graph and silently drops out of the schedule. Worse, if you use len(order) < number_of_nodes_seen as your cycle check, the missing task doesn’t trigger it, because the graph doesn’t know it exists. In Course Schedule problems, courses with no prerequisites are exactly this case. Initialise every node from the full task list (or range(numCourses)) before reading edges.
Many valid orders
A DAG usually has many topological orders. In the example, docs can go anywhere, and lint can run any time after install. Kahn’s algorithm with a FIFO queue returns one of them, determined by the order nodes were added. If a problem wants a specific order, for instance the alphabetically smallest, replace the queue with a min-heap so you always take the smallest ready task:
alphabetical tie-break: ['docs', 'install', 'codegen', 'compile', 'lint', 'package', 'test', 'deploy']That costs O(log V) per heap operation, so O(V log V + E) overall. Build tools that want reproducible output do something similar.
The other classic approach is depth-first. Run DFS from every unvisited node and record each node when it finishes (after all its dependents are explored). Reversing that finish order gives a topological order:
DFS reverse postorder: ['docs', 'install', 'lint', 'codegen', 'compile', 'package', 'test', 'deploy']A node finishes only after everything reachable from it has finished, so in reverse finish order every node appears before everything that depends on it. Both approaches are O(V + E). Kahn’s algorithm is iterative, so it doesn’t hit recursion limits on long dependency chains, and it extends naturally to scheduling in rounds, which is the practice problem below. The DFS version is the one to use if you also need to report the exact cycle.
Interview practice: minimum number of semesters
There are n courses labelled 1 to n. Each relation [a, b] means course a must be taken before course b. In one semester you can take any number of courses, as long as you’ve completed all their prerequisites in earlier semesters. Return the minimum number of semesters needed to take every course, or -1 if it’s impossible. For n = 3 and relations [[1, 3], [2, 3]], the answer is 2.
Answer
Run Kahn’s algorithm, but process the queue one level at a time, the same trick used for level-order BFS. Everything in the queue at the start of a round has no unmet prerequisites, so all of it can be taken this semester. Courses that become ready while processing the round go into the queue for the next semester. Count the rounds, and use the number of courses taken to detect a cycle.
from collections import deque
def minimum_semesters(n, relations):
graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
for before, after in relations:
graph[before].append(after)
indegree[after] += 1
queue = deque(c for c in range(1, n + 1) if indegree[c] == 0)
semesters = taken = 0
while queue:
semesters += 1
for _ in range(len(queue)): # everything available this semester
c = queue.popleft()
taken += 1
for nxt in graph[c]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt) # available next semester
return semesters if taken == n else -1
print(minimum_semesters(3, [[1, 3], [2, 3]]),
minimum_semesters(3, [[1, 2], [2, 3], [3, 1]]),
minimum_semesters(5, []),
minimum_semesters(6, [[1, 2], [2, 3], [3, 4], [1, 5], [5, 4], [4, 6]]))2 -1 1 5The second input is a three-course cycle, so nothing ever becomes available and the answer is -1. With no relations, all five courses fit in one semester. The last case has two routes to course 4, 1 → 2 → 3 → 4 and 1 → 5 → 4; the longer one decides, giving 5 semesters for the chain 1, 2, 3, 4, 6.
That last observation is the deeper point worth saying out loud: the minimum number of rounds equals the number of nodes on the longest path in the DAG. Taking every ready course immediately is optimal because delaying a course can only delay the courses that depend on it. Time is O(V + E) and space O(V + E). The plain yes/no version of this problem is Course Schedule, which you can solve with either Kahn’s algorithm or three-state DFS.
Related notes
- Data Structures and Algorithms interview questions
- DSA multiple-choice questions
- Graph DFS States and Cycle Detection
- Breadth-First Search and Unweighted Shortest Paths, the same level-by-level queue technique
- MIT 6.006 Introduction to Algorithms (Spring 2020), lecture 10 (depth-first search)