DFS Post-Order Topological Sort
Run DFS and push each node to a stack after its neighbours are fully explored, then pop the stack for a valid topological order.
DFS Post-Order Topological Sort is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
DFS-Based Topological Sort Idea
The second classical topological sort algorithm uses DFS with post-order processing. After fully exploring all neighbours of a node (and their descendants), push the node onto a stack. When all nodes are processed, pop the stack to read the topological order. A node pushed to the stack after all its dependencies means it comes first in the order — so the reversed post-order is the topological sort.
Intuition Behind Post-Order
Consider a dependency graph where course A requires course B. When DFS visits A, it first recurses into B. B has no prerequisites, so it finishes first and gets pushed first. Then A finishes and gets pushed. Popping the stack gives A before B in the output — but we reverse at the end, giving B before A: take B first, then A. Post-order pushes dependencies before dependents, so the reversed stack is a valid topological order.
Three-Colour DFS for Cycle Detection
Use three states for visited: WHITE (0) = unvisited, GREY (1) = currently being processed (in the DFS call stack), BLACK (2) = fully processed. A back edge — an edge to a GREY node — indicates a cycle. Edges to BLACK nodes are safe (they were already fully explored). This three-colour scheme correctly detects all cycles in directed graphs.
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)Full DFS Topological Sort Implementation
Use a recursive DFS that colours nodes, pushes to a stack in post-order, and returns False on cycle detection. After visiting all nodes, the stack (reversed) gives the topological order.
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Iterative DFS to Avoid Stack Overflow
Python's recursion limit (default 1000) is a concern for large graphs. An iterative DFS using an explicit stack avoids this. The trick: push (node, False) initially; when popped with False, push (node, True) (meaning 'I'll return here after exploring') and push all unvisited neighbours with False. When popped with True, colour it BLACK and push to result stack.
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]DFS vs Kahn's: Comparison
Both run in O(V + E). Key differences: Kahn's (BFS) naturally produces nodes in earliest-dependency-first order and has simpler cycle detection (len check). DFS post-order works recursively and detects back edges explicitly. Kahn's is preferred when you want the result in forward order without reversing. DFS is preferred when you need the full post-order for other purposes (like SCC detection). Both are acceptable in interviews.
Post-Order on a Tree vs a DAG
In a tree, post-order visits left subtree → right subtree → root. In a DAG, post-order DFS visits all dependencies of a node before processing the node itself — the same idea generalised to multiple predecessors and arbitrary graph structure. The root of a DFS tree (the starting node) gets pushed last among its descendants, making it appear first in the reversed stack — the correct topological position for a node with no predecessors.
Alien Dictionary (LeetCode 269)
Alien Dictionary: given a sorted list of words in an alien language, derive the character ordering. Compare adjacent words character by character to find the first difference — this gives an edge c1 → c2 meaning c1 comes before c2. Collect all such edges and run topological sort to produce the alien character ordering. If a cycle exists, the ordering is invalid.
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'Topological Sort with Constraints
Some problems ask for a topological sort satisfying additional constraints, like maintaining relative order of elements from the original list. Combine Kahn's algorithm with a custom priority queue or pre-sorting: keep elements in original relative order by using a stable sort on the queue contents at each step. These constrained variants test deeper understanding of the algorithm's flexibility.
Recognising Topological Sort Problems
Signal phrases in interview problems that indicate topological sort: 'given dependencies', 'prerequisites', 'task ordering', 'build order', 'can all tasks be completed?', 'find a valid sequence'. If the problem involves an ordering of items where some must come before others, build a directed graph and apply Kahn's or DFS topological sort. Cycle detection is often a secondary requirement in the same problem.
Comparing DFS and Kahn's Output
DFS and Kahn's can produce different valid topological orders for the same graph. Both are correct — a DAG can have multiple valid topological orderings. To verify correctness, check that for every edge u → v in the graph, u appears before v in the output order. For interview problems that require a specific order (e.g., lexicographically smallest), use Kahn's with a min-heap — DFS post-order does not naturally produce the lex-smallest order.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: DFS post-order topological sort pushes nodes after all their dependencies are explored, three-colour marking (WHITE/GREY/BLACK) detects cycles via back edges to GREY nodes, and reversing the post-order stack gives a valid topological ordering. Next up we apply topological sort directly to the Course Schedule problems I and II.
Frequently asked questions
Is the “DFS Post-Order Topological Sort” lesson free?
Yes — the full text of “DFS Post-Order Topological Sort” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “DFS Post-Order Topological Sort”?
Run DFS and push each node to a stack after its neighbours are fully explored, then pop the stack for a valid topological order. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “DFS Post-Order Topological Sort” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Kahn's Algorithm: BFS Topological Sort
- DFS Post-Order Topological Sort
- Course Schedule I and II
- Strongly Connected Components with Kosaraju