GeeksforGeeks Medium

Topological Sort (DFS)

Topologically order a DAG using DFS finish times instead of in-degrees.

graphtoposortdfspost-order

02

Intuition

A vertex is only safe to record once everything it points to is finished. So append it on the way out of the recursion, not on the way in. That produces an order where every vertex appears after all its descendants — reverse it, and every edge points forward.

How to spot this pattern

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.

03

Approach

1

Record on exit, not entry

dfs(v): recurse into all unvisited neighbours first, then append v. This post-order guarantees each vertex is appended only after its whole reachable set.

2

Reverse the finish order

In the finish list a vertex sits after its descendants. Reversing puts it before them, which is exactly the topological requirement that edges point forward.

3

Kahn's vs DFS

Same result, different mechanics: Kahn's is iterative and detects cycles naturally; DFS is shorter but needs a separate grey/black check to spot cycles.

04

Solution & live demo

▶1def topo_sort_dfs(n, adj):
▶2    seen = [False] * n
▶3    finished = []
▶4    def dfs(v):
▶5        seen[v] = True            # entering
▶6        for u in adj[v]:
▶7            if not seen[u]:
▶8                dfs(u)
▶9        finished.append(v)        # all descendants done
▶10    for s in range(n):
▶11        if not seen[s]:
▶12            dfs(s)
▶13    return finished[::-1]         # reverse the finish order

05

Common pitfalls

Appending on entry instead of on finish

✗ Wrong

def dfs(v):
    seen[v] = True
    finished.append(v)
    for u in adj[v]: ...

✓ Right

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

✗ Wrong

return finished

✓ Right

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

✗ Wrong

dfs(0)
return finished[::-1]

✓ Right

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.

06

Edge cases

Disconnected DAG

Outer loop starts DFS from every unvisited vertex; all components appear.

Cycle present

This plain version does not detect it — pair with the grey/black cycle check when input may be cyclic.

Single vertex

Finishes immediately; reversal is a no-op.

07

Complexity

Time

O(V + E)

Space

O(V)

One DFS pass plus a reversal.