Introduction

A DFS-based topological sort normally relies on recursion: visit a node, recursively visit its outgoing neighbors, then add the node to the result after all descendants are done. To avoid recursion, you can simulate that call stack explicitly. The trick is to keep per-node visit state so you know whether a node is being entered for the first time or finished after exploring its neighbors.

The Core Idea

For a directed acyclic graph, a topological order can be produced by placing each node into the output only after all outgoing neighbors have been processed.

The recursive DFS version does that naturally using the program's call stack. The iterative version must store that state explicitly.

A common approach uses three states:

• '0: unvisited'
• '1: currently in the DFS stack'
• '2: fully processed'

This also makes cycle detection possible. If you encounter an edge to a node in state 1, the graph is not acyclic.

Iterative DFS Algorithm

The idea is to push frames onto an explicit stack. Each frame keeps:

• the current node
• whether we are entering it or finishing it

A clean Python implementation looks like this:

1def topo_sort_dfs_iterative(graph):
2    state = {node: 0 for node in graph}
3    order = []
4
5    for start in graph:
6        if state[start] != 0:
7            continue
8
9        stack = [(start, False)]
10
11        while stack:
12            node, processed = stack.pop()
13
14            if processed:
15                state[node] = 2
16                order.append(node)
17                continue
18
19            if state[node] == 2:
20                continue
21
22            if state[node] == 1:
23                raise ValueError("Graph contains a cycle")
24
25            state[node] = 1
26            stack.append((node, True))
27
28            for neighbor in reversed(graph[node]):
29                if state[neighbor] == 1:
30                    raise ValueError("Graph contains a cycle")
31                if state[neighbor] == 0:
32                    stack.append((neighbor, False))
33
34    order.reverse()
35    return order
36
37graph = {
38    "A": ["B", "C"],
39    "B": ["D"],
40    "C": ["D"],
41    "D": []
42}
43
44print(topo_sort_dfs_iterative(graph))

The processed flag plays the role of the return step in recursive DFS.

Why the Two-Phase Stack Entry Works

When a node is first popped with processed=False, we:

1. mark it as in progress
2. push a second frame saying "finish this node later"
3. push its neighbors for traversal first

When the later processed=True frame is popped, all reachable descendants have already been handled, so the node can be added safely to the output.

That exactly mirrors recursive postorder traversal.

A Small Walkthrough

For this graph:

1A -> B
2A -> C
3B -> D
4C -> D

The algorithm might process nodes in a stack order such that:

• 'D finishes first'
• then B
• then C
• then A

Reversing that finishing order gives a valid topological order.

This is why topological sort from DFS is often described as "reverse postorder."

Why Use This Instead of Kahn's Algorithm?

Kahn's algorithm is another excellent non-recursive topological sort method based on indegrees and a queue. You would choose iterative DFS when:

• you specifically want DFS semantics
• you already have DFS-oriented graph infrastructure
• you want a direct non-recursive replacement for the recursive textbook algorithm

If you only need a topological order and do not care about DFS structure, Kahn's algorithm is often simpler to explain.

Implementation Details That Matter

The reversed(graph[node]) part is not required for correctness. It just makes the output order more predictable relative to the adjacency-list order.

Also note that every node must appear in the graph dictionary, even if it has no outgoing edges. Otherwise, the state table and traversal logic become inconsistent.

Common Pitfalls

The most common mistake is using an explicit stack but forgetting the second "processed" phase. If you append nodes immediately on first visit, the result is not a valid DFS topological order.

Another mistake is skipping cycle detection. Topological sort is defined only for DAGs, so the implementation should detect back edges.

Developers also often forget to reverse the final order. DFS finishing order itself is the reverse of the desired topological sequence.

Finally, be careful with graphs where some nodes appear only as neighbors. Make sure every vertex is represented in the graph structure.

Summary

• A non-recursive DFS topological sort uses an explicit stack to simulate recursive calls.
• Track node states so you know whether a node is unvisited, in progress, or finished.
• Append nodes only after all outgoing neighbors are processed.
• Reverse the finishing order to obtain the topological order.
• Include cycle detection because a graph with a cycle has no valid topological sort.