Kahn's algorithm and DFS-based topo sort — prerequisite and dependency problems.
Published September 21, 2026
Some tasks can only happen after others: a course after its prerequisites, a build step after the modules it depends on, a database migration after the one before it. Model each task as a node and each "must come before" as a directed edge u → v. A topological order is a line-up of all the nodes in which every edge points forward: u appears before v.
Two facts drive everything:
The in-degree of a node is the number of edges pointing into it, which is how many prerequisites it still has. Nodes with in-degree 0 have no remaining prerequisites and can go next. Taking one "removes" its outgoing edges, which may free up other nodes.
public List<Integer> topoSort(int n, int[][] edges) { // edges[i] = {from, to}
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indegree = new int[n];
for (int[] e : edges) { adj.get(e[0]).add(e[1]); indegree[e[1]]++; }
Deque<Integer> ready = new ArrayDeque<>();
for (int v = 0; v < n; v++) if (indegree[v] == 0) ready.add(v);
List<Integer> order = new ArrayList<>();
while (!ready.isEmpty()) {
int u = ready.poll();
order.add(u);
for (int v : adj.get(u)) {
if (--indegree[v] == 0) ready.add(v); // last prerequisite done → v is ready
}
}
return order.size() == n ? order : List.of(); // fewer than n → a cycle blocked some nodes
}
Cycle detection comes free: nodes on a cycle never reach in-degree 0, so they're never output. If the order has fewer than n nodes, the graph has a cycle.
Complexity: O(V + E) time, since every node and edge is processed once, and O(V + E) space for the adjacency list.
LeetCode's version gives prerequisites[i] = [course, prereq], meaning prereq → course. Get the edge direction right; reversing it is the most common bug.
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[][] edges = new int[prerequisites.length][];
for (int i = 0; i < prerequisites.length; i++)
edges[i] = new int[]{prerequisites[i][1], prerequisites[i][0]}; // prereq → course
List<Integer> order = topoSort(numCourses, edges);
return order.stream().mapToInt(Integer::intValue).toArray(); // empty if impossible
}
// "Can you finish all courses?" (Course Schedule I) is just: order.size() == numCourses
Run DFS, and add a node to the result after all of its descendants have been added (post-order). Reversing that post-order gives a topological order: a node finishes only after everything that depends on it has finished.
Cycle detection needs three colours. White means unvisited, gray means on the current DFS path, and black means finished. Meeting a gray node means you've followed an edge back into the current path, which is a cycle:
private static final int WHITE = 0, GRAY = 1, BLACK = 2;
public List<Integer> topoSortDfs(int n, List<List<Integer>> adj) {
int[] color = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int v = 0; v < n; v++)
if (color[v] == WHITE && !dfs(v, adj, color, stack)) return List.of(); // cycle
return new ArrayList<>(stack); // stack top = first in topological order
}
private boolean dfs(int u, List<List<Integer>> adj, int[] color, Deque<Integer> stack) {
color[u] = GRAY;
for (int v : adj.get(u)) {
if (color[v] == GRAY) return false; // back edge → cycle
if (color[v] == WHITE && !dfs(v, adj, color, stack)) return false;
}
color[u] = BLACK;
stack.push(u); // post-order
return true;
}
A plain boolean visited array isn't enough for cycle detection in a directed graph. Reaching an already-finished (black) node through a different path is fine; only a node still on the current path (gray) means a cycle.
Kahn or DFS? Both are O(V + E). Kahn's is iterative (no stack overflow on deep graphs), naturally produces levels, and is easy to adapt, for example using a priority queue for the lexicographically smallest order. DFS is compact and is the basis for related algorithms such as strongly connected components.
Parallel scheduling / minimum semesters. Process Kahn's queue level by level. Everything ready at the same time can run in parallel, and the number of levels is the minimum number of rounds.
Lexicographically smallest order. Replace the queue with a PriorityQueue, so the smallest ready node is always taken next.
Is the order unique? It's unique only if the ready queue never holds more than one node at a time. If there's a choice at any moment, several orders exist.
Alien Dictionary: build the graph yourself.
Words are sorted in an unknown alphabet: ["wrt","wrf","er","ett","rftt"]. Find a valid letter order.
Compare each adjacent pair of words. The first position where they differ gives one edge, earlier letter → later letter. Nothing after that position tells you anything.
public String alienOrder(String[] words) {
Map<Character, Set<Character>> adj = new HashMap<>();
Map<Character, Integer> indegree = new HashMap<>();
for (String w : words) for (char c : w.toCharArray()) { adj.putIfAbsent(c, new HashSet<>()); indegree.putIfAbsent(c, 0); }
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i + 1];
if (a.length() > b.length() && a.startsWith(b)) return ""; // "abc" before "ab" is invalid
for (int j = 0; j < Math.min(a.length(), b.length()); j++) {
char x = a.charAt(j), y = b.charAt(j);
if (x != y) {
if (adj.get(x).add(y)) indegree.merge(y, 1, Integer::sum); // avoid double-counting duplicate edges
break; // only the FIRST difference matters
}
}
}
Deque<Character> ready = new ArrayDeque<>();
indegree.forEach((c, d) -> { if (d == 0) ready.add(c); });
StringBuilder order = new StringBuilder();
while (!ready.isEmpty()) {
char c = ready.poll();
order.append(c);
for (char next : adj.get(c)) if (indegree.merge(next, -1, Integer::sum) == 0) ready.add(next);
}
return order.length() == indegree.size() ? order.toString() : ""; // cycle → no valid alphabet
}
// → "wertf"
Three edge cases decide this problem: a word followed by its own prefix is invalid input, duplicate edges must not inflate in-degrees, and a cycle means no valid order.
Build tools (Maven, Gradle, Bazel) order module builds. Package managers resolve install order. Spreadsheets recalculate cells after the cells they reference. Workflow engines and DAG schedulers (Airflow) run tasks after their upstream tasks. Database migration tools and ORMs order table creation around foreign keys.
Q: How do you detect a cycle with topological sort? A: With Kahn's algorithm, if the output contains fewer nodes than the graph, the remaining nodes are stuck on or behind a cycle. With DFS, reaching a node that's currently on the recursion stack (gray) is a back edge, which means a cycle.
Q: Why doesn't a simple visited flag detect cycles in directed graphs?
A: A node can legitimately be reached twice through different paths without a cycle (a diamond shape). Only reaching a node that's still on the current path indicates a cycle, which is why DFS needs the extra "in progress" state.
Q: What's the time complexity? A: O(V + E) for both algorithms. Each node is enqueued or visited once, and each edge is examined once.
Q: How would you find the minimum number of semesters to finish all courses? A: Run Kahn's algorithm level by level (all currently ready nodes form one semester). The number of levels is the answer, or it's impossible if a cycle stops progress. With a limit of k courses per semester, it becomes a harder problem, often solved with bitmask DP for small n.
Q: Can a topological order be computed incrementally as edges are added? A: Yes, with dynamic topological-ordering algorithms that only reorder the affected region when a new edge would violate the current order. Many practical systems instead simply recompute, because V + E is small.