Topological Sort via DFS Departure Time

Topological Sort via DFS Departure Time turns the recursion of a depth-first search into an ordering. The key realization: the order in which DFS finishes vertices, reversed, is a valid topological order of a DAG.

The slow way first

A natural first idea is Kahn's algorithm: repeatedly find a vertex with in-degree 0, output it, and remove its outgoing edges. That works and is O(V + E), but it needs an explicit in-degree table and a queue you keep refilling.

The question to ask: is there an ordering already hidden in a plain DFS? It turns out there is — we just have to watch when each vertex finishes, not when it starts.

The idea: record departure (finish) times

Run a normal DFS. A vertex finishes (we call this its departure time) only after all of its descendants have finished. So a vertex always finishes after everything it can reach. That means: if u → v, then v finishes before u. Sort by descending finish time and every edge points forward.

The clean trick: append each vertex to a list the moment it finishes, then reverse the list at the end (or prepend as you go).

Because a finished vertex can never be reached by a still-unfinished one in a DAG, descending finish time is guaranteed acyclic-consistent.

Walk through it

Step through the animation. DFS starts at A, dives A → C → F. F is a sink, so it finishes first (departure 1) and is prepended. Then C finishes, then D, then A. A fresh DFS starts at B, reaches E, and finally B finishes last (departure 6). The order, built by prepending each finisher, is [B, E, A, D, C, F].

Pseudocode

visited = empty set
order = empty list
for each vertex u in the graph:
    if u not visited:
        dfs(u)
 
dfs(u):
    mark u visited
    for each neighbor v of u:
        if v not visited:
            dfs(v)
    append u to order      # u just finished — record departure
 
return reverse(order)      # descending finish time

The Python solution

def topo_sort(graph):
    visited = set()
    order = []
 
    def dfs(u):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                dfs(v)
        order.append(u)        # u finishes here
 
    for u in graph:
        if u not in visited:
            dfs(u)
    return order[::-1]         # reverse finish order

• visited stops us re-exploring a vertex; order collects vertices in finish order.
• The inner dfs recurses into every unvisited neighbor before doing anything with u itself.
• Line 10 is the heart: order.append(u) runs only after the loop over neighbors completes, so u is recorded after all its descendants — that is its departure time.
• The outer loop restarts DFS from any vertex that a previous tree never reached (here, B).
• Line 15 reverses the finish order, turning "last to finish first" into "sources first" — the topological order.

Complexity

Same asymptotic cost as Kahn's algorithm, but it falls out of a plain DFS with no in-degree bookkeeping — just one append at the end of each call.

When this pattern shows up

Practice