--- title: "Topological Sort" description: "DAG ordering with DFS and Kahn's algorithm" source: https://vizlearn.app/algorithms/graph/topological-sort access: premium (interactive player requires Lifetime; this doc is free) --- # Topological Sort Topological sort arranges every vertex of a directed acyclic graph so each edge points from an earlier vertex to a later one. Kahn's algorithm removes zero-indegree sources; depth-first search records vertices on return and reverses that finish order. Both run in O(V + E) time, and both reject directed cycles. Think of course prerequisites. You may take a course only after every incoming prerequisite has disappeared from your checklist. Kahn works from the courses available now. DFS starts a course-planning chain, follows it to the end, then writes the plan backward while returning. ## How topological sort works Kahn asks, "What may run now?" DFS asks, "What can be safely placed at the back?" They look from opposite ends of the same constraint. A topological order must satisfy one invariant: for every directed edge `u -> v`, `u` appears before `v`. The order need not be unique. If two courses have no remaining prerequisites, either may come first unless some outside rule breaks the tie. Kahn's algorithm stores the **remaining indegree** of every vertex. It puts every vertex with indegree zero into a queue, removes one source, appends it to the answer, and subtracts one from each outgoing neighbor. A neighbor enters the queue at the exact moment its count reaches zero. If the queue empties before the answer contains every vertex, the leftover vertices contain a directed cycle, plus any vertices blocked downstream of it. DFS reaches the same invariant from the other end. A vertex is marked active when its call starts and finished only after every outgoing neighbor has finished. The algorithm appends the vertex at that return point. That list has dependents before prerequisites, so reversing it produces the topological order. An edge to an active ancestor is a cycle, not an invitation to recurse forever. Choose Kahn when failure diagnostics matter. If its queue stalls, the unprocessed residual contains the cycle and identifies the tasks still blocked by cyclic dependencies, which is useful in build tools. Kahn is also iterative, so a long dependency chain cannot exhaust the call stack. Choose DFS when recursive traversal already fits the surrounding code or when you are already maintaining active and finished states. ## Topological sort step by step The default animation uses Kahn's algorithm on six vertices with these edges: `A->C`, `B->C`, `B->D`, `C->E`, `D->E`, `D->F`, and `E->F`. 1. Count incoming edges. The indegrees are `A=0`, `B=0`, `C=2`, `D=1`, `E=2`, and `F=2`. 2. Seed the FIFO queue with the two available sources: `[A, B]`. The tie is resolved by letter order for a deterministic trace; it is not a new graph constraint. 3. Dequeue and emit `A`. Removing `A->C` lowers `C` from 2 to 1. One prerequisite remains, so C stays out of the queue. 4. Dequeue and emit `B`. Removing `B->C` lowers C from 1 to 0, so C enters the queue. Removing `B->D` lowers D from 1 to 0, so D follows it. The queue is now `[C, D]`, and the output is `[A, B]`. 5. Emit `C`. Its edge to E lowers `E` from 2 to 1. E is still blocked. 6. Emit `D`. Now `D->E` lowers E to zero and unlocks it, while `D->F` lowers F from 2 to 1. The queue contains `[E]`. 7. Emit `E`. Removing `E->F` lowers F to zero, so F enters the queue. Emit F last. 8. The queue is empty and all six vertices were emitted. Kahn returns `[A, B, C, D, E, F]`. 9. The verification tail places vertices in that order and scans all seven edges from left to right. It then lays out DFS's order, `[B, D, A, C, E, F]`, and repeats the scan. Both pass. Kahn constructs an order when the graph is acyclic; an order whose edges all point right cannot contain a cycle, because following rightward edges can never return to the start. Switch to DFS without changing the graph. DFS finishes vertices in the order `[F, E, C, A, D, B]`; reversing that list returns `[B, D, A, C, E, F]`. This answer differs from Kahn's, but every edge still points forward in both. The graph has several valid schedules. The visual signal is the same invariant in two costumes. In Kahn mode, watch an `in=k` badge reach zero and move into the queue. In DFS mode, watch a vertex enter the finish row only after its descendants turn green. ## Time and space complexity | Variant | Time complexity | Extra space | What each edge does | | --- | --- | --- | --- | | Kahn | O(V + E) | O(V) | increments one indegree during setup, then decrements it once | | DFS | O(V + E) | O(V) | is inspected once during recursive traversal | Both variants also store the graph itself in O(V + E) space. Kahn's O(V) auxiliary storage is the indegree table, queue, and output. DFS uses a three-state table, a finish list, and up to O(V) call-stack frames on a long chain. There is no meaningful comparison-based lower bound hiding here. Reading the graph already costs O(V + E), and both algorithms meet that bill exactly. ## Edge cases - **One vertex, no edges:** both algorithms return that vertex. - **Several vertices, no edges:** every permutation is a valid topological order. Deterministic code still chooses one repeatable result. - **A single chain:** the order is unique because every vertex except the first has exactly one earlier prerequisite. - **Disconnected DAG:** process every component. DFS needs an outer loop over all vertices; starting from one vertex is only a reachability search. - **Self-loop or directed cycle:** no topological order exists. Kahn leaves vertices unprocessed; DFS finds an edge to an active vertex. ## Common mistakes - **Enqueuing at indegree one.** A positive indegree means at least one prerequisite is still missing. Only the transition to zero unlocks the vertex. - **Marking a Kahn vertex visited when it is first seen.** Kahn is not ordinary BFS. The count, not a visited flag, decides when a vertex becomes available. - **Appending on DFS entry.** That produces preorder, which can place a dependent before another prerequisite. Append on return, then reverse. - **Using one DFS visited bit for cycle detection.** You must distinguish active from finished. An edge to active proves a cycle; an edge to finished is harmless. - **Returning Kahn's partial list after the queue stalls.** Check that the output length equals `V`. A plausible prefix is still not a topological order of the whole graph.