Order vertices in a directed acyclic graph so that every edge points forward, solving dependency and scheduling problems in O(V + E).
A topological sort produces a linear ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before v in the ordering. If the graph has a cycle, no valid topological order exists.
Think of tasks with prerequisites. You cannot start task B until task A finishes. Topological sort gives you a valid execution order that respects all such dependencies.
Why DAG only? If the graph contains a cycle (e.g., A→B→C→A), there is no way to place all three vertices in order. Detecting cycles is a critical part of topological sort: Kahn's algorithm detects a cycle when the output has fewer vertices than the graph, while DFS detects it via back-edges.
Look for these recognition signals in the problem statement. If you spot one, topological sort is very likely the intended approach.
"prerequisites" or "dependencies"
"ordering" or "sequence from rules"
"cycle detection" in a directed graph
"parallel scheduling" or "minimum semesters"
The key clue: You have a directed graph where you need to process nodes in an order that respects all directed edges. A brute-force approach would try every permutation O(V!). Topological sort solves it in O(V + E) by systematically processing nodes with no remaining unresolved dependencies.
Kahn's algorithm works by repeatedly removing nodes that have zero in-degree (no remaining prerequisites). When we remove a node, we decrement the in-degree of all its neighbors. This is the most intuitive and commonly used variant.
Graph: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1. Find a valid topological order.
Cycle detection with Kahn's: After the algorithm finishes, if the output contains fewer than V nodes, the graph has a cycle. The remaining nodes all participate in a cycle where none can reach in-degree 0.
Run DFS from every unvisited node. When a node's DFS finishes (all descendants processed), push it onto a stack. After all DFS calls, the stack (top to bottom) gives the topological order. This leverages the fact that a node's post-order time is always after all of its dependencies.
DFS starting from node 5, then node 4 (arbitrary unvisited order).
Choosing the variant: Use Kahn's (BFS) when you need to detect cycles easily, find the lexicographically smallest order (use a min-heap), or process nodes level-by-level (e.g., minimum semesters). Use DFS when the graph is represented via adjacency lists and you want a simple recursive solution or need to detect back-edges for cycle checking.
Here are the annotated Java templates for both variants. Choose the one that best fits the problem constraints.
// Kahn's Algorithm — BFS-based Topological Sort int[] topoSortKahn(int V, List<List<Integer>> adj) { int[] indegree = new int[V]; for (int u = 0; u < V; u++) for (int v : adj.get(u)) indegree[v]++; // count incoming edges Queue<Integer> q = new LinkedList<>(); for (int i = 0; i < V; i++) if (indegree[i] == 0) q.offer(i); // start from zero-indegree int[] order = new int[V]; int idx = 0; while (!q.isEmpty()) { int u = q.poll(); order[idx++] = u; // add to result for (int v : adj.get(u)) { indegree[v]--; if (indegree[v] == 0) q.offer(v); // new zero-indegree node } } return idx == V ? order : new int[0]; // empty = cycle }
// DFS-based Topological Sort int[] topoSortDFS(int V, List<List<Integer>> adj) { boolean[] visited = new boolean[V]; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < V; i++) if (!visited[i]) dfs(i, adj, visited, stack); int[] order = new int[V]; for (int i = 0; i < V; i++) order[i] = stack.pop(); // reverse post-order return order; } void dfs(int u, List<List<Integer>> adj, boolean[] visited, Deque<Integer> stack) { visited[u] = true; for (int v : adj.get(u)) if (!visited[v]) dfs(v, adj, visited, stack); stack.push(u); // post-order: push after children }
Cycle detection in DFS: Add a visiting[] (gray) array alongside visited[] (black). If you encounter a node that is currently in the "visiting" state, you have found a back-edge, which means a cycle exists. Return false immediately.
Let us trace through Kahn's algorithm on a different graph step by step, showing the queue, in-degrees, and output at every stage.
A classic diamond DAG. Node 0 has no prerequisites. Node 3 depends on both 1 and 2.
| STEP | ACTION | QUEUE | IN-DEGREES | OUTPUT |
|---|---|---|---|---|
| Init | Compute in-degrees, enqueue 0 | [0] | [0:0, 1:1, 2:1, 3:2] | [] |
| 1 | Dequeue 0, decrement 1 and 2 | [1, 2] | 0:0, 1:0, 2:0, 3:2 | [0] |
| 2 | Dequeue 1, decrement 3 | [2] | 3:1 | [0, 1] |
| 3 | Dequeue 2, decrement 3 | [3] | 3:0 | [0, 1, 2] |
| 4 | Dequeue 3, no neighbors | [] | all zero | [0, 1, 2, 3] |
Notice the pattern: Each vertex is enqueued exactly once (when its in-degree hits 0) and dequeued exactly once. Each edge is examined exactly once (when we decrement in-degrees). Total work: O(V + E).
These are the classic LeetCode problems that use topological sort, listed in rough order of difficulty.
Practice tip: Start with #207 (pure cycle detection via topological sort) and #210 (return the actual order). Once comfortable, try #269 which requires you to build the graph from character comparisons before applying topological sort. #1136 uses BFS topological sort level-by-level to find the minimum number of semesters.
Define edges of a DAG and step through Kahn's algorithm. Watch in-degrees update, the queue fill and drain, and the output order build up.
Both Kahn's and DFS variants visit every vertex exactly once and examine every edge exactly once. Computing in-degrees requires iterating all edges: O(E). The BFS loop processes each vertex once O(V) and each edge once O(E) when decrementing in-degrees. Total: O(V + E).
Space: The adjacency list takes O(V + E). The in-degree array and queue (or visited array and recursion stack) take O(V). The output array takes O(V). Total: O(V + E).
Kahn's vs DFS performance: Both are O(V + E). Kahn's uses a queue (iterative, no stack overflow risk). DFS uses recursion, which can hit stack limits on very deep graphs with hundreds of thousands of nodes. For large inputs, prefer Kahn's or convert DFS to iterative form.
DAG = Topological Sort exists. A topological ordering exists if and only if the graph is a DAG (directed acyclic graph). Both algorithms double as cycle detectors: Kahn's checks output size, DFS checks for back-edges.
Kahn's for BFS-level grouping and cycle detection. Kahn's algorithm naturally provides the "level" (distance from sources) of each node, making it ideal for problems like "minimum semesters" or "parallel task scheduling."
DFS for simple recursive implementation. DFS-based topological sort is concise and works well when cycle detection is done separately or when you need post-order processing. Add a "visiting" state for three-color cycle detection.
Build the graph first. Many problems do not give you an explicit adjacency list. You must construct the graph from the problem description (e.g., character ordering in Alien Dictionary, prerequisite pairs in Course Schedule).
Use a min-heap for lexicographic order. If the problem asks for the lexicographically smallest topological order, replace the queue in Kahn's algorithm with a priority queue (min-heap). This ensures you always process the smallest available node first.