Graph algorithms · Interview prep
Socks go on before shoes. You cannot deploy code that has not been built. You cannot take Machine Learning before its prerequisites. Topological sort is the algorithm that turns rules like these into one valid order, and it shows up in interviews all the time.
What is topological sort?
Imagine getting ready in the morning. You have a list of things to do, and some of them depend on others: socks before shoes, shirt before jacket, shower before shirt. You do not care about the exact order of things that do not depend on each other. You only need an order where every task comes after the tasks it depends on.
That is a topological sort. Formally, it is a linear ordering of the nodes of a directed graph such that for every arrow u → v, node u appears before node v. In a graph, each task is a node and each "must come first" rule is an arrow.
One-line definition. Topological sort lines up the nodes of a directed graph so that every arrow points from left to right.
Most graphs have many valid orders. If you can put on socks and a shirt in either order, both answers are correct. The algorithm gives you one of them.
Why it only works on DAGs (no cycles)
Suppose task A needs task B, and task B needs task A. Neither can start. Nobody can be first, so no valid order exists. This situation is called a cycle.
A topological order exists if and only if the graph is a DAG, a Directed Acyclic Graph: arrows have a direction, and you can never follow them and end up back where you started. A good topological sort routine therefore also answers a second question for free: "does this graph have a cycle?"
Where topological sort is used
- Build tools such as Maven, Gradle and Make compile modules after the modules they depend on.
- Course scheduling decides in which order to take subjects with prerequisites.
- Package managers install a library's dependencies before the library itself.
- Spreadsheets recalculate a cell only after the cells its formula refers to.
- Data pipelines such as Airflow run each job after the jobs it reads from.
Words you need to know
| Term | Plain meaning |
|---|---|
| Node (vertex) | One task, course or module. |
| Edge | An arrow u → v meaning "u must come before v". |
| In-degree | How many arrows point into a node, or how many unfinished prerequisites it has. |
| DAG | A directed graph with no cycles. |
| Source node | A node with in-degree 0. It is free to start right now. |
Kahn's algorithm, stage by stage
Kahn's algorithm is the easiest way to understand topological sort, and the one most interviewers expect. The idea is simple: keep taking out tasks that have nothing left blocking them.
- Count the in-degree of every node.
- Put every node with in-degree 0 into a queue.
- Take a node out of the queue and add it to the answer. Erase its outgoing arrows, which lowers the in-degree of its neighbours by 1.
- Any neighbour that reaches in-degree 0 goes into the queue. Repeat step 3 until the queue is empty.
Our running example is a small course plan. The letters A to E are the same as node numbers 0 to 4 in the Java code later.
- A, Intro, is required for B (Data Structures) and C (Math).
- B and C are both required for D (Algorithms).
- D is required for E (ML).
The final answer is A, B, C, D, E. C could also have come before B, and that would be equally correct. If the queue ever empties before every node is placed, the graph has a cycle.
Kahn's algorithm in Java
This is the method to memorise for interviews. It runs in O(V + E) time, where V is the number of nodes and E the number of edges, because each node enters the queue once and each edge is looked at once.
// ---------- Method 1: Kahn's Algorithm (BFS using in-degrees) ----------
// Returns the topological order, or an empty list if the graph has a cycle.
static List<Integer> kahnTopologicalSort(int n, List<List<Integer>> adj) {
int[] indegree = new int[n];
for (int u = 0; u < n; u++) {
for (int v : adj.get(u)) {
indegree[v]++;
}
}
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int u = queue.poll();
order.add(u);
for (int v : adj.get(u)) {
if (--indegree[v] == 0) {
queue.offer(v);
}
}
}
// If we could not place every node, a cycle exists.
return order.size() == n ? order : Collections.emptyList();
}Read it in three chunks. The first loop builds the in-degree array. The second loop seeds the queue. The while loop is stages 3 to 7 from the diagrams. The last line is the cycle check: if fewer nodes were placed than exist, something is stuck in a cycle.
To try it yourself, here is the helper that builds the graph and a main method for the example graph above.
static List<List<Integer>> buildGraph(int n) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
return adj;
}
public static void main(String[] args) {
// Example graph: 0->1, 0->2, 1->3, 2->3, 3->4 (A=0, B=1, C=2, D=3, E=4)
List<List<Integer>> adj = buildGraph(5);
adj.get(0).add(1);
adj.get(0).add(2);
adj.get(1).add(3);
adj.get(2).add(3);
adj.get(3).add(4);
System.out.println("Kahn : " + kahnTopologicalSort(5, adj));
System.out.println("DFS : " + dfsTopologicalSort(5, adj));
System.out.println("Smallest: " + smallestTopologicalOrder(5, adj));
System.out.println("canFinish(2, [[1,0]]) = " + canFinish(2, new int[][]{{1, 0}}));
System.out.println("canFinish(2, [[1,0],[0,1]]) = " + canFinish(2, new int[][]{{1, 0}, {0, 1}}));
}Kahn : [0, 1, 2, 3, 4]
DFS : [0, 2, 1, 3, 4]
Smallest: [0, 1, 2, 3, 4]
canFinish(2, [[1,0]]) = true
canFinish(2, [[1,0],[0,1]]) = falseDFS-based topological sort
The second classic method uses depth-first search. Think of it this way: a task is only finished after everything that depends on it has finished. So if you write down tasks in the order they finish and then reverse that list, prerequisites come first.
In code, a stack does the reversing for you. A node is pushed onto the stack after all its neighbours are done, and the top of the stack is the first task.
// ---------- Method 2: DFS-based topological sort ----------
// state: 0 = unvisited, 1 = visiting (on current path), 2 = done
static List<Integer> dfsTopologicalSort(int n, List<List<Integer>> adj) {
int[] state = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (state[i] == 0 && !dfs(i, adj, state, stack)) {
return Collections.emptyList(); // cycle found
}
}
return new ArrayList<>(stack); // top of stack first = valid order
}
private static boolean dfs(int u, List<List<Integer>> adj, int[] state, Deque<Integer> stack) {
state[u] = 1;
for (int v : adj.get(u)) {
if (state[v] == 1) return false; // back edge -> cycle
if (state[v] == 0 && !dfs(v, adj, state, stack)) return false;
}
state[u] = 2;
stack.push(u); // push AFTER all descendants are finished
return true;
}Notice the three states: 0 means not seen yet, 1 means "on my current path", 2 means finished. If DFS meets a node that is still in state 1, it has walked in a circle, which is exactly a cycle. The output differs from Kahn's ([0, 2, 1, 3, 4]), and it is still correct.
Detecting cycles with topological sort
Many interview questions are secretly cycle detection. Run Kahn's algorithm and compare the number of placed nodes with the total. Here is the picture of a failing case:
The famous LeetCode problem Course Schedule asks exactly this: can you finish all courses given the prerequisites?
// ---------- Method 3: Cycle detection (LeetCode 207: Course Schedule) ----------
static boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = buildGraph(numCourses);
for (int[] p : prerequisites) {
adj.get(p[1]).add(p[0]); // p[1] must be taken before p[0]
}
return kahnTopologicalSort(numCourses, adj).size() == numCourses;
}Watch the edge direction. A prerequisite pair [1, 0] means "to take course 1 you must first take course 0", so the arrow goes from 0 to 1. Getting this backwards is the most common bug.
Getting the smallest valid order
Sometimes the interviewer wants the lexicographically smallest order, or "always do the lowest-numbered available task first". Swap the plain queue for a min-heap and the rest stays the same. It costs O((V + E) log V).
// ---------- Method 4: Lexicographically smallest order ----------
static List<Integer> smallestTopologicalOrder(int n, List<List<Integer>> adj) {
int[] indegree = new int[n];
for (int u = 0; u < n; u++) for (int v : adj.get(u)) indegree[v]++;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) if (indegree[i] == 0) pq.offer(i);
List<Integer> order = new ArrayList<>();
while (!pq.isEmpty()) {
int u = pq.poll();
order.add(u);
for (int v : adj.get(u)) if (--indegree[v] == 0) pq.offer(v);
}
return order.size() == n ? order : Collections.emptyList();
}Kahn vs DFS, and complexity
| Kahn's algorithm (BFS) | DFS with stack | |
|---|---|---|
| Main idea | Repeatedly remove nodes with in-degree 0 | Push a node after all its descendants finish |
| Time | O(V + E) | O(V + E) |
| Extra space | O(V) for in-degrees and queue | O(V) for state array, stack and recursion |
| Cycle detection | Placed count is less than V | Meeting a node that is still "in progress" |
| Deep graphs | Safe, no recursion | Can overflow the call stack |
| Good when | You need level-by-level processing or the smallest order | You already use DFS or want short code |
Common mistakes
- Reversed edges. Read the problem statement twice to decide which way the arrow points.
- Forgetting disconnected parts. Start DFS from every unvisited node, or seed Kahn's queue with every in-degree 0 node.
- Skipping the cycle check. Without it you can return a short, wrong answer.
- Assuming one answer. Valid orders are usually not unique, so tests should check validity, not equality.
- Recursion depth. A chain of 100,000 nodes can crash recursive DFS in Java. Prefer Kahn's algorithm or an iterative DFS.
5 important interview questions
Try each one on your own first. Open the hint only when you are stuck.
1. Is this a valid topological order?
You are given a directed graph and a sequence of all its nodes. Return true if the sequence is a valid topological order.
Show hint
Store each node's position in a map. For every edge u → v, check that pos[u] < pos[v]. One pass over the edges, O(V + E).
2. Course Schedule (LeetCode 207)
There are numCourses courses and a list of prerequisite pairs. Can you finish all of them?
Show hint
Build the graph, run Kahn's algorithm, and return true only if every course was placed. The solution is the canFinish method shown above.
3. Course Schedule II (LeetCode 210)
Same input as above, but return an actual order in which to take the courses, or an empty array if it is impossible.
Show hint
Return the order list from Kahn's algorithm when its size equals the number of courses. Handle the empty-prerequisites case, where any order works.
4. Parallel Courses: minimum semesters (LeetCode 1136)
You can take any number of courses in one semester as long as their prerequisites were finished in earlier semesters. What is the minimum number of semesters to finish everything, or -1 if impossible?
Show hint
Process Kahn's algorithm level by level. Everything in the queue at the start of a round is taken in the same semester. Count the rounds. If not all courses were taken, return -1.
5. Alien Dictionary (LeetCode 269)
You get a list of words sorted in an unknown alien alphabet. Work out the order of the letters.
Show hint
- Compare each pair of neighbouring words and find the first position where they differ. That gives one edge
a → bmeaning "a comes before b". - Watch out for the trap case where a longer word comes before its own prefix (for example "abc" before "ab"). That input is invalid, so return an empty string.
- Run a topological sort over all distinct letters. If a cycle exists, the ordering is impossible.
.jpg)
.jpg)
