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.

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

python

▶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

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.

06

Complexity

Time

O(V + E)

Space

O(V)

One DFS pass plus a reversal.