AdvancedData Structures & Algorithms · Lesson 29 of 29 · Updated ·
Topological Sort — Kahn's BFS, DFS Order, Cycle Detection and Course Schedule
Your college says: take C before Data Structures, Maths before Data Structures, Data Structures before Algorithms and Operating Systems, and C before DBMS. In what order can you take the courses? Build systems (which file to compile first), package managers (which library to install first) and spreadsheet formulas (which cell to compute first) all ask the same question. The answer is a topological sort.
1. The problem
Model each task as a node and each rule "u must come before v" as a directed edge u → v. A topological order lists all nodes so that every edge points forward (u appears before v).
Two facts to remember:
- An order exists only if the graph has no cycle. If A needs B and B needs A, nobody can start. A directed graph with no cycle is called a DAG (directed acyclic graph).
- The order is usually not unique. Maths and C can be taken in either order.
2. Kahn's algorithm (BFS with in-degrees)
The in-degree of a node is the number of edges coming into it — its number of unfinished prerequisites.
- Compute every in-degree. Put all nodes with in-degree 0 in a queue.
- Take a node from the queue and add it to the answer.
- "Remove" its outgoing edges: lower the in-degree of each neighbour by 1. Any neighbour that drops to 0 joins the queue.
- Repeat until the queue is empty.
Cycle check for free: if the answer has fewer nodes than the graph, some nodes never reached in-degree 0. They are stuck in (or behind) a cycle.
from collections import deque
def topo_kahn(nodes, edges):
adj = {n: [] for n in nodes}
indeg = {n: 0 for n in nodes}
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
q = deque(n for n in nodes if indeg[n] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == len(nodes) else None # None = cycle
courses = ["Maths", "C", "DS", "DBMS", "Algo", "OS"]
rules = [("C", "DS"), ("Maths", "DS"), ("DS", "Algo"),
("Maths", "Algo"), ("C", "DBMS"), ("DS", "OS")]
print(topo_kahn(courses, rules))
print(topo_kahn(["A", "B", "C"], [("A", "B"), ("B", "C"), ("C", "B")]))
['Maths', 'C', 'DS', 'DBMS', 'Algo', 'OS']
None
Time is O(V + E): each node enters the queue once and each edge is looked at once. If you need the smallest order in dictionary order, replace the queue with a min-heap.
3. The DFS method
Run DFS. When a node finishes (all its descendants are done), push it onto a list. The reverse of the finishing order is a topological order — a node finishes only after everything that depends on it has finished.
To detect a cycle, give each node one of three colours:
| Colour | Meaning |
|---|---|
| white (0) | not visited yet |
| gray (1) | on the current DFS path, still in progress |
| black (2) | finished |
Reaching a gray node means we came back to a node on our own path: that is a cycle. Reaching a black node is fine — it is just a shared prerequisite.
import sys
sys.setrecursionlimit(10000)
def topo_dfs(nodes, edges):
adj = {n: [] for n in nodes}
for u, v in edges:
adj[u].append(v)
color = {n: 0 for n in nodes}
out = []
def dfs(u):
color[u] = 1
for v in adj[u]:
if color[v] == 1:
return False # back edge: cycle
if color[v] == 0 and not dfs(v):
return False
color[u] = 2
out.append(u) # u is finished
return True
for n in nodes:
if color[n] == 0 and not dfs(n):
return None
return out[::-1]
courses = ["Maths", "C", "DS", "DBMS", "Algo", "OS"]
rules = [("C", "DS"), ("Maths", "DS"), ("DS", "Algo"),
("Maths", "Algo"), ("C", "DBMS"), ("DS", "OS")]
print(topo_dfs(courses, rules))
['C', 'DBMS', 'Maths', 'DS', 'OS', 'Algo']
This is a different order from Kahn's, and it is also correct: check that every rule points forward.
4. Course schedule in Java
The classic interview version: n courses numbered 0..n−1 and pairs [a, b] meaning "to take a, first take b". Can you finish all courses? (Course Schedule I.) Return one valid order. (Course Schedule II.) Both are Kahn's algorithm; note the edge goes b → a.
import java.util.*;
public class Main {
static int[] findOrder(int n, int[][] prereq) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] p : prereq) { // p = {course, needs}
adj.get(p[1]).add(p[0]);
indeg[p[0]]++;
}
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
int[] order = new int[n];
int k = 0;
while (!q.isEmpty()) {
int u = q.poll();
order[k++] = u;
for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
}
return k == n ? order : new int[0]; // empty = impossible
}
public static void main(String[] args) {
System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
System.out.println(Arrays.toString(findOrder(2, new int[][]{{1, 0}, {0, 1}})));
}
}
[0, 1, 2, 3]
[]
5. Where topological order helps
- Scheduling with dependencies: courses, build steps, project tasks.
- DP on a DAG: longest path, number of paths, or earliest finish time. Process nodes in topological order so every node's inputs are ready. Longest path in a general graph is very hard, but on a DAG it is O(V + E).
- Alien dictionary: compare neighbouring words to get "letter x comes before letter y" edges, then topologically sort the letters.
Common mistakes
- Reversing the edge direction for course pairs.
[a, b]= "a needs b" = edge b → a. - Forgetting the cycle check: Kahn's must compare
len(order)with the number of nodes. - In DFS cycle detection, using only visited/not-visited. A visited (black) node is not a cycle; only a gray one is.
- Forgetting nodes with no edges at all. They have in-degree 0 and belong in the answer.
- Returning the DFS finishing order without reversing it.
Quick recap
- Topological order: every edge u → v has u before v. It exists only for a DAG and is often not unique.
- Kahn's: queue the in-degree-0 nodes, remove them one by one, lowering neighbours' in-degrees.
- DFS: reverse of finishing order; a gray node reached again means a cycle.
- Both run in O(V + E). Fewer nodes in the output than in the graph means a cycle.