A topological order of a directed acyclic graph (DAG) is an ordering of its vertices such that every edge points forward. Equivalently: if there's an edge from to , then comes before in the ordering. Useful whenever dependencies determine sequence — task scheduling, course prerequisites, build systems, formula evaluation in spreadsheets.
Kahn's algorithm (BFS-based)
1. Compute the in-degree (number of incoming edges) for each vertex. 2. Initialize a queue with all in-degree 0 vertices. 3. Repeatedly: dequeue, append to the order, decrement in-degree of each neighbor; enqueue any whose in-degree becomes 0.
If the order has fewer vertices than the graph, a cycle exists. .
DFS-based
Run DFS. When a vertex finishes (post-order), prepend it to the output list. The reverse post-order is a valid topological order. Also . Cycle detection requires tracking the recursion stack.
When the graph isn't a DAG
Both algorithms detect cycles. Without acyclicity, no topological order exists; the algorithms simply report failure.
Multiple valid orders
A DAG generally has many valid topological orders. Kahn's algorithm with a sorted queue (use a min-heap) produces the lexicographically smallest order — often what you want when ties need breaking.
Common application: course schedule
Given pairs of prerequisites, can you complete all courses? Run topological sort; if it succeeds, return the order. If it fails, the prerequisites contain a cycle. This is one of the most-asked variants in coding interviews.