What Is Topological Sort
Topological sort is a linear ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge u→v, vertex u appears before vertex v in the ordering. It answers the question: given a set of tasks with prerequisites, in what order should they be executed?
Topological sort is only possible on directed acyclic graphs. If the graph contains a cycle — for example, A depends on B and B depends on A — no valid linear ordering exists. This is precisely why LeetCode 207 (Course Schedule) asks whether it is possible to finish all courses: it is asking whether the prerequisite graph is a DAG.
The ordering produced by topological sort is not unique. If multiple nodes have no incoming edges at a given point, any of them can come next. This means there can be many valid topological orderings for the same graph, and algorithms like Kahn's BFS may produce different valid results depending on tie-breaking.
- Linear ordering of DAG vertices where every edge u→v has u before v
- Only possible on directed acyclic graphs — cycles make it impossible
- Not unique: multiple valid orderings may exist
- Applications: course prerequisites, build systems, task scheduling, package dependency resolution
- Graph must be directed — undirected graphs use connected components instead
Kahn's Algorithm (BFS)
Kahn's algorithm computes topological sort iteratively using BFS. First, compute the in-degree (number of incoming edges) for every node. Add all nodes with in-degree 0 to a queue — these are the nodes with no prerequisites. Process the queue: for each node popped, append it to the result list, then decrement the in-degree of all its neighbors. If any neighbor's in-degree drops to 0, add it to the queue.
Continue until the queue is empty. The result list is a valid topological ordering. If the result contains all n nodes, the graph is a DAG and topological sort succeeded. If the result contains fewer than n nodes, a cycle exists — the remaining nodes are stuck in the cycle and their in-degrees never reached 0.
Kahn's algorithm runs in O(V + E) time — each vertex and edge is processed once. The BFS structure is iterative and easy to reason about. It produces a valid topological order and simultaneously detects cycles, making it the most practical choice for interviews.
- 1Compute in-degree for every node by scanning all edges
- 2Add all nodes with in-degree 0 to a queue
- 3While queue is not empty: pop a node, append to result
- 4For each neighbor of the popped node: decrement its in-degree
- 5If a neighbor's in-degree becomes 0, add it to the queue
- 6After queue empties: if len(result) == n, valid DAG; else cycle detected
Kahn's BFS Is the Go-To
Kahn's BFS is the go-to for interviews: it naturally detects cycles and produces the ordering in one pass. If len(result) < n after BFS, a cycle exists. O(V + E) time, easy to implement.
Cycle Detection with Kahn's
Cycle detection is a natural byproduct of Kahn's algorithm. Nodes in a cycle always have in-degree greater than zero relative to each other — no node in the cycle can become a zero-in-degree node first. So when the BFS queue empties, any node not in the result is part of a cycle.
LeetCode 207 (Course Schedule I) asks: given numCourses and a list of prerequisites, is it possible to finish all courses? This is equivalent to asking whether the prerequisite graph is a DAG. Run Kahn's BFS and check if len(result) == numCourses. If yes, return true; if no, return false. The actual ordering does not matter.
LeetCode 210 (Course Schedule II) extends this: return the actual course order. Run Kahn's BFS fully and return the result list if its length equals numCourses, otherwise return an empty array. The result list from Kahn's is directly the valid course ordering.
- 1Build adjacency list and in-degree map from prerequisites
- 2Initialize queue with all courses having in-degree 0 (no prerequisites)
- 3BFS: pop course, append to order, decrement neighbors' in-degrees
- 4Push any neighbor whose in-degree drops to 0 into the queue
- 5After BFS: if len(order) == numCourses → return order (or True)
- 6If len(order) < numCourses → cycle exists, return [] (or False)
DFS Approach
The DFS approach to topological sort works by running depth-first search from each unvisited node. After fully exploring all descendants of a node — i.e., in post-order — append the node to a result list. After all DFS calls complete, reverse the result list to get the topological order.
The reason post-order reversal works: a node is added to the result only after all its dependencies (outgoing neighbors in a DAG) are fully explored. So dependencies always appear after the current node in the un-reversed list, and after reversal, they appear before it — exactly the topological order requirement.
For cycle detection in DFS, use 3-state coloring: WHITE (unvisited), GRAY (currently in DFS stack), BLACK (fully processed). If DFS encounters a GRAY node, a back edge exists, indicating a cycle. If it encounters a BLACK node, that branch is already fully processed — skip it. Only WHITE nodes are explored fresh.
- 1Initialize all nodes as WHITE (unvisited)
- 2For each unvisited node, run DFS
- 3Mark node GRAY (in-progress) at start of DFS
- 4Recurse on all unvisited neighbors; if a GRAY neighbor found → cycle detected
- 5Mark node BLACK (done) after all neighbors processed
- 6Append node to result in post-order, then reverse result for topological order
DFS Post-Order Reversal
DFS post-order reversal works because a node is added only after all its dependencies are fully explored. Reversing the post-order list guarantees every dependency appears before the node that requires it.
Kahn's vs DFS
Kahn's BFS and DFS post-order reversal both produce valid topological orderings in O(V + E) time, but they have different characteristics. Kahn's is iterative, easier to implement without a recursion stack, and its cycle detection is explicit — just compare result length to node count. DFS is recursive, uses the call stack implicitly, and cycle detection requires 3-state coloring.
For interviews, Kahn's is generally preferred because the logic is more linear and the cycle detection is self-evident. You compute in-degrees, drain the queue, and check the count. DFS topological sort requires careful handling of the 3-state coloring and the post-order reversal step, which is less intuitive under pressure.
That said, DFS topological sort is more flexible in some contexts. Problems that require grouping nodes by depth level, or that naturally integrate with recursive DFS traversal, may be easier with the DFS approach. Alien Dictionary (LC 269) can be solved with either, but understanding both opens more problem-solving options.
- 1Kahn's BFS: iterative, queue-based, in-degree computation, explicit cycle check
- 2DFS: recursive, post-order reversal, 3-state coloring for cycle detection
- 3Kahn's cycle detection: len(result) < n → cycle exists
- 4DFS cycle detection: GRAY node encountered during DFS → cycle
- 5Both: O(V + E) time, O(V + E) space
- 6Interview default: Kahn's BFS — simpler logic, clearer cycle detection
Common LeetCode Applications
Course Schedule I (LC 207) and Course Schedule II (LC 210) are the canonical topological sort problems. LC 207 returns a boolean — can all courses be finished? LC 210 returns the actual order. Both are solved with Kahn's BFS. The prerequisite list is the edge list; build the adjacency list and in-degree map, then run BFS.
Alien Dictionary (LC 269) presents a sorted list of words from an alien language. By comparing adjacent words character by character, you can infer ordering constraints between letters (letter X must come before letter Y). These constraints form a DAG — run topological sort to recover the alien alphabet order. A cycle means the input is invalid.
Beyond LeetCode, topological sort is fundamental in real-world systems: build tools like Make and Bazel compute build order from dependency graphs; package managers (npm, pip) resolve install order; compilers determine evaluation order for expressions. Recognizing that a dependency resolution problem reduces to topological sort is a key interview insight.
Cycle vs Order Problems
If the problem asks "is it possible to finish all X?" use Kahn's and check len(result) == n. If it asks "return the order," use Kahn's or DFS post-order. Either way, cycle detection is the key first step.