Topological sort
Order the nodes of a dependency graph so every edge points forward, and detect cycles for free.
Course Schedule II. There are n courses. prereqs[i] = [a, b] means you must take b before a. Return an order to take all courses, or [] if it is impossible.
Signals that point here
- Dependencies, prerequisites, build order, task scheduling, package installs.
- "Is there a cycle in this directed graph?"
- Alien dictionary: derive an order from pairwise comparisons.
The idea
Kahn's algorithm: repeatedly take a node with no remaining prerequisites (in-degree 0), output it, and remove its outgoing edges. If you run out of such nodes before outputting all n, the rest sit on a cycle.
The alternative is DFS post-order (reverse the finish order, with a three-colour visited state to catch back edges). Kahn's is easier to get right under pressure and gives cycle detection directly; mention both.
from collections import deque
def course_order(n: int, prereqs: list[list[int]]) -> list[int]:
indegree = [0] * n
after: list[list[int]] = [[] for _ in range(n)]
for course, before in prereqs:
after[before].append(course)
indegree[course] += 1
queue = deque(c for c in range(n) if indegree[c] == 0)
order = []
while queue:
c = queue.popleft()
order.append(c)
for nxt in after[c]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == n else [] # short = cyclepublic static class Topological
{
public static List<int> CourseOrder(int n, int[][] prereqs)
{
var indegree = new int[n];
var after = Enumerable.Range(0, n).Select(_ => new List<int>()).ToArray();
foreach (var p in prereqs) { after[p[1]].Add(p[0]); indegree[p[0]]++; }
var queue = new Queue<int>(Enumerable.Range(0, n).Where(c => indegree[c] == 0));
var order = new List<int>();
while (queue.Count > 0)
{
int c = queue.Dequeue();
order.Add(c);
foreach (int next in after[c])
if (--indegree[next] == 0) queue.Enqueue(next);
}
return order.Count == n ? order : new List<int>(); // short = cycle
}
}Complexity
O(V + E) time and space.
Pitfalls interviewers watch for
- Reversing the edge direction:
[a, b]meansb -> a. - Forgetting the cycle check and returning a partial order.
- Claiming the order is unique. Many valid orders usually exist; the interviewer may accept any.
Variants worth knowing
- Course Schedule I: return only whether
len(order) == n. - Alien dictionary: an edge from the first differing letter of each adjacent word pair.
- Parallel scheduling: process the queue level by level to get the minimum number of semesters.
Test it like the interviewer will
course_order(2, [[1, 0]])returns[0, 1]course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])returns[0, 1, 2, 3]course_order(2, [[0, 1], [1, 0]])returns[]course_order(3, [])returns[0, 1, 2]- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: course_order(6, [[1, 0], [2, 0], [3, 1], [3, 2], [4, 3], [5, 4], [5, 2]])
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Given a sorted list of words in an unknown alphabet, return a valid letter order.
- Return the minimum number of semesters to finish all courses if any number can be taken at once.
- Detect a cycle in a directed graph using DFS colours instead of in-degrees.
Check yourself
How does Kahn's algorithm detect a cycle?
Fewer than n nodes are output: the remainder never reach in-degree 0.
What is the cost?
O(V + E).