Topological Sort — Ordering with Dependencies
Learn how to order tasks with prerequisites using Kahn’s algorithm or DFS post-order, and recognise when topological sort applies.
Problem Statement
Given a directed acyclic graph (DAG), produce an ordering of vertices such that every directed edge U → V places U before V.
Why This Problem Matters
- Course scheduling, build systems, and dependency resolution are all topo-sort questions.
- Demonstrates ability to detect cycles and reason about DAGs.
- Topological ordering is often the foundation for dynamic programming on DAGs.
Thought Process
Count incoming edges (indegrees)
Vertices with zero indegree can appear first. Removing them reduces indegrees of neighbors.
Choose algorithm: BFS (Kahn) or DFS post-order
Kahn’s algorithm uses a queue and explicit indegree updates. DFS records finishing order reversed.
Detect cycles early
If you exhaust the queue before ordering all vertices, a cycle exists and no topological order is possible.
Step-by-Step Reasoning
- Compute indegree for every vertex.
- Push all zero-indegree vertices into a queue.
- Repeatedly pop from the queue, append to order, and decrement indegree of neighbors.
- If a neighbor’s indegree drops to zero, enqueue it. Verify all nodes were processed.
Dry Run
Edges: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1
Kahn’s algorithm outputs [4,5,0,2,3,1] (one of multiple valid orders).
Graph with cycle 1→2→3→1
Queue empties before processing all nodes, revealing the cycle.
Complexity Analysis
Time
O(V + E)
Space
O(V)
Why
Each node and edge is processed once; the queue holds at most all vertices.
Annotated Solution
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
public class TopologicalSorter {
public static List<Integer> topoSort(int numVertices, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>(numVertices);
for (int i = 0; i < numVertices; i += 1) {
adj.add(new ArrayList<>());
}
int[] indegree = new int[numVertices];
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
adj.get(u).add(v);
indegree[v] += 1;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numVertices; i += 1) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int neighbor : adj.get(node)) {
indegree[neighbor] -= 1;
if (indegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
return order.size() == numVertices ? order : Collections.emptyList();
}
}Kahn’s algorithm makes cycle detection explicit: if some vertices remain with indegree > 0, no valid ordering exists.
Common Pitfalls
- Forgetting to initialise indegrees to zero leads to incorrect queue seeding.
- Appending to the result before checking indegree 0 can emit nodes prematurely.
- Returning partial orders without verifying count hides cycles instead of reporting them.
Follow-Up Questions
- Use DFS post-order to generate a topological sort and compare with Kahn’s algorithm.
- Explain how to detect cycles explicitly by tracking recursion stack in DFS.
- Apply topological ordering to evaluate expression dependencies or build pipelines.