Topological Sort (DFS)
Topological Sort (DFS): topologically order a DAG using DFS finish times instead of in-degrees.
- 1 <= V <= 10⁴
- 0 <= E <= 10⁵
- Graph must be a DAG; reverse the finish order to get the answer
Intuition
Topological sort dfs orders a directed acyclic graph so that every edge points forward. The DFS approach reaches that ordering through a detail that is easy to state and easy to get backwards: when a vertex is recorded.
Think about when a vertex is safe to place. It cannot be output before anything it points to has been settled — those successors must come after it, so their positions have to be known first. The moment that condition holds is when the recursion is leaving the vertex, not entering it:
- Append each vertex on the way out of the recursion, after all its descendants are finished.
That produces a list where every vertex sits after everything reachable from it — the exact reverse of what a topological order requires. So reverse the list at the end and every edge points forward.
Recording on entry instead is the classic mistake. It produces an order based on discovery rather than completion, which happens to look right on simple chains and quietly fails on any branching graph.
One limitation is worth being explicit about. This algorithm assumes a DAG and does not detect cycles on its own — a cycle produces a wrong answer rather than an error. Detecting one requires tracking which vertices are currently on the recursion stack, the grey/black colouring. Kahn's BFS version, by contrast, detects cycles for free: if fewer than V vertices are output, a cycle exists.
A node is safe to output only once everything it depends on is already placed — which is exactly when its DFS finishes. So record nodes at finish time and reverse at the end. Recognising that post-order finish times encode dependency order is what makes this five lines instead of Kahn's queue-and-indegree bookkeeping.
Approach
Before reading on: price up what the direct approach costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(V + E) time and O(V) space.
Record on exit, not on entry
In dfs(v), recurse into every unvisited neighbour first, then append v. Appending on entry orders by discovery rather than completion, which is the single most common way this algorithm is written wrong.
Understand what post-order guarantees
A vertex is appended only after everything reachable from it, so in the finish list it sits after all its descendants. That is precisely the reverse of a topological order — which is why the next step exists.
Reverse the finish list
Reversing puts each vertex before its descendants, so every edge points forward. Using a stack and pushing instead of appending achieves the same thing, since popping yields the reversed order naturally.
Start from every unvisited vertex
A DAG may be disconnected or have several sources, so loop over all vertices and launch a DFS from each unvisited one. A single traversal only covers what one start vertex reaches.
Know that cycles are not detected
This algorithm assumes a DAG and produces a wrong answer rather than an error on a cyclic graph. Detecting a cycle needs a separate grey/black check tracking vertices currently on the recursion stack.
Compare with Kahn's algorithm
Kahn's BFS version repeatedly removes zero-in-degree vertices and detects cycles for free — if fewer than V vertices come out, one exists. DFS is shorter to write; Kahn's is iterative and self-validating.
Cost of the traversal
Every vertex and edge is visited once, giving O(V + E) time and O(V) space for the visited array, the output list and the recursion stack.
Solution & live demo
Common pitfalls
Appending on entry instead of on finish
def dfs(v):
seen[v] = True
finished.append(v)
for u in adj[v]: ...def dfs(v):
seen[v] = True
for u in adj[v]:
if not seen[u]: dfs(u)
finished.append(v)Recording on entry gives pre-order, which says nothing about dependencies — a node lands in the list before the nodes it points to are even explored. The guarantee only holds at the moment every descendant has finished.
Forgetting to reverse the finish order
return finished
return finished[::-1]
Finishing order puts the deepest dependencies first, which is the exact reverse of a valid topological order. The last node to finish has nothing depending on it, so it belongs at the front.
Starting DFS only from node 0
dfs(0) return finished[::-1]
for s in range(n):
if not seen[s]: dfs(s)A directed graph can have several components and several sources, so one start node may not reach everything. Every unvisited vertex needs its own launch.
Edge cases
Outer loop starts DFS from every unvisited vertex; all components appear.
This plain version does not detect it — pair with the grey/black cycle check when input may be cyclic.
Finishes immediately; reversal is a no-op.