Iterative DFS, in depth: explicit stack frames, finish times, the two shortcuts that break, and an iterative Tarjan SCC

The idea in one picture

What a recursive call actually stores

Look at what a recursive DFS keeps on the call stack. Each active call holds two things: the vertex it is visiting, and how far it has got through that vertex's adjacency list. When a child call returns, the parent resumes its loop at the next neighbour, not from the start. The code after the loop, where finish time and postorder are recorded, runs only once every neighbour has been handled.

So a faithful iterative version needs a stack of frames, each holding a vertex and a cursor into its neighbours. At every step you look at the top frame, advance its cursor to the next unvisited neighbour and push a new frame for it; if the cursor is exhausted, you pop the frame and run the post-visit code. The stack holds at most one frame per vertex on the current path, so memory is O(V) in the worst case, the same as recursion, but on the heap where it can grow to millions of entries.

The faithful conversion in code

In Python the cursor can be the adjacency iterator itself. The for ... else construct expresses the step exactly: the for advances the cursor until it finds a white vertex and breaks; the else runs only if the iterator was exhausted.

def dfs_iterative(adj):
    '''adj: list of neighbour lists. Returns pre, post, discovery and finish times.'''
    n = len(adj)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    pre, post = [], []
    disc, fin = [0] * n, [0] * n
    clock = 0
    for s in range(n):
        if color[s] != WHITE:
            continue
        color[s] = GRAY
        clock += 1; disc[s] = clock; pre.append(s)
        stack = [(s, iter(adj[s]))]
        while stack:
            u, it = stack[-1]
            for v in it:                       # resume u's loop where it stopped
                if color[v] == WHITE:
                    color[v] = GRAY
                    clock += 1; disc[v] = clock; pre.append(v)
                    stack.append((v, iter(adj[v])))
                    break                      # "recursive call": go deeper
            else:                              # u has no unvisited neighbours left
                stack.pop()
                color[u] = BLACK
                clock += 1; fin[u] = clock; post.append(u)
    return pre, post, disc, fin

In languages without resumable iterators, or when you want the stack in flat arrays for speed, store an integer index instead. Two parallel arrays avoid allocating a tuple per frame, which matters in Java or Go on large graphs:

// Java-style: frames as two int arrays; adjacency in CSR form (offsets, targets)
int top = 0;
stackV[top] = s; stackI[top] = offsets[s]; seen[s] = true; onEnter(s);
while (top >= 0) {
    int u = stackV[top];
    if (stackI[top] < offsets[u + 1]) {
        int v = targets[stackI[top]++];        // advance this frame's cursor
        if (!seen[v]) {
            seen[v] = true; onEnter(v);
            top++; stackV[top] = v; stackI[top] = offsets[v];
        }
    } else {
        onExit(u);                             // postorder, finish time
        top--;
    }
}

Both versions visit neighbours in adjacency-list order and produce the same preorder, postorder, discovery and finish times as the recursive function. That equivalence is worth testing directly: generate random graphs, sort the adjacency lists, and assert that all four outputs match. The tests behind this article did that for 2,000 random directed graphs, and also ran the iterative version on a 1,000,000-vertex chain that the recursive version could not handle.

Worked trace

Use the graph in the diagram: 0 to 1 and 2; 1 to 3; 2 to 3 and 4; 4 to 1. Start at 0 with clock 0.

Preorder is 0 1 3 2 4 and postorder 3 1 4 2 0. Edges into BLACK vertices with a smaller discovery time, 2 to 3 and 4 to 1, are cross edges; an edge into a GRAY vertex would be a back edge and prove a cycle. Reversing the postorder gives 0 2 4 1 3, a valid topological order. The BFS and DFS overview covers edge classification in more depth.

Two shortcuts and what they break

Most iterative DFS code in the wild is one of two shortcuts, and both look fine on small tests.

Shortcut A: mark on pop, push all neighbours. Pop a vertex; if it is already marked, skip it; otherwise mark it, record it, and push all its unmarked neighbours in reverse order. This does produce the same preorder as recursive DFS, which is why it survives code review. But a vertex can sit on the stack many times, so the stack grows to O(E) rather than O(V), and there is no moment at which a vertex is known to be finished. You cannot compute postorder, finish times, low-links or the GRAY state, so it cannot detect directed cycles or produce a topological order.

Shortcut B: mark on push. Mark neighbours as visited when they are pushed, to keep the stack small. Now a vertex is claimed by the first vertex that sees it, not the first that descends into it. On the triangle 0 to 1, 0 to 2, 1 to 2, true DFS goes 0, 1, 2 and the tree edge into 2 comes from 1. Mark-on-push marks both 1 and 2 while expanding 0, so 2's parent becomes 0 and the edge 1 to 2 is no longer a tree edge. The traversal still reaches every vertex, so reachability and connected components remain correct, but the tree is not a DFS tree, and anything built on DFS tree properties, such as bridges, articulation points or low-link SCCs, silently returns wrong answers.

Use the shortcuts only for reachability, flood fill or counting components, where any traversal order works. For anything else, use frames.

Iterative Tarjan SCC

Tarjan's strongly connected components algorithm is the hardest common case to make iterative, because work happens at three points: when entering a vertex, after each child returns (propagate the child's low-link to the parent), and when leaving (pop a component if the vertex is a root). With frames, the after-child step moves to the moment a frame is popped: the new top is the parent.

def tarjan_scc(adj):
    n = len(adj)
    index, low = [-1] * n, [0] * n
    on_stack = [False] * n
    comp_stack, sccs, counter = [], [], 0
    for s in range(n):
        if index[s] != -1:
            continue
        index[s] = low[s] = counter; counter += 1
        comp_stack.append(s); on_stack[s] = True
        call = [(s, 0)]
        while call:
            u, i = call[-1]
            if i < len(adj[u]):
                call[-1] = (u, i + 1)
                v = adj[u][i]
                if index[v] == -1:                    # tree edge: "recurse"
                    index[v] = low[v] = counter; counter += 1
                    comp_stack.append(v); on_stack[v] = True
                    call.append((v, 0))
                elif on_stack[v]:                     # edge into current component
                    low[u] = min(low[u], index[v])
            else:
                call.pop()
                if call:                              # the "after child returns" step
                    parent = call[-1][0]
                    low[parent] = min(low[parent], low[u])
                if low[u] == index[u]:                # u is a component root
                    comp = []
                    while True:
                        w = comp_stack.pop(); on_stack[w] = False
                        comp.append(w)
                        if w == u:
                            break
                    sccs.append(comp)
    return sccs

Note the two stacks: call replaces the language's call stack, while comp_stack is part of Tarjan's algorithm and exists in the recursive version too. Confusing them is the classic bug. The tested version returns exactly the same components in the same order as the recursive one. For the algorithm itself, see Tarjan's SCC algorithm.

Alternatives to rewriting

Rewriting is not the only option. In Python you can raise sys.setrecursionlimit and run the search in a thread created after threading.stack_size() has been set to a large value; this keeps recursive code but couples correctness to an interpreter setting, and each CPython frame is far larger than a tuple on a list. On the JVM you can start a thread with an explicit stack size in its constructor, which the documentation says may be ignored on some platforms. In native code you can raise ulimit -s or the thread attribute. All of these move the limit rather than remove it, and they fail far from the code that caused it.

An explicit stack also buys things recursion cannot: you can pause and resume a search (useful for incremental or time-sliced work), inspect the current path at any time (it is the stack), bound memory explicitly, and cancel cleanly. For trees specifically, Morris traversal avoids the stack entirely by temporarily rewiring pointers.

Failure modes

• Postorder recorded at push time. Recording a vertex as finished when it is pushed or first popped gives a wrong topological order, often only on graphs with shared descendants. Record finish only when the frame's cursor is exhausted.
• Restarting the neighbour loop. Storing only the vertex and rescanning its adjacency from the start on every visit to the top frame makes the search O(V times degree) and can be quadratic on stars. Store the cursor.
• Mutating adjacency during traversal. An iterator over a list that changes underneath it skips or repeats neighbours. Freeze the graph or copy the list into the frame.
• Different order from the recursive version. Pushing all neighbours forward instead of reversed changes the visiting order. That is harmless for reachability but breaks tests and deterministic outputs; decide which order you want and test it.
• Forgetting the outer loop. A single DFS from vertex 0 misses unreachable vertices; topological sort and SCC need a loop over all start vertices.

Trade-offs

Recursive DFS is clearer, and for bounded depth, such as balanced trees, ASTs or small graphs, it is the right choice. The frame-based iterative version costs a little readability and nothing in asymptotic time: O(V + E) either way. For directed acyclic graphs where you only need an order, Kahn's algorithm avoids DFS entirely; topological sort two ways compares both, and directed cycle detection uses the GRAY state shown here.

What to do next

1. Search your codebase for recursive graph and tree walks over user-controlled or unbounded input; those are latent crashes.
2. Replace them with the frame-and-cursor pattern, keeping the pre-visit and post-visit code in the same places.
3. Write a property test: random graphs, sorted adjacency, assert iterative and recursive outputs are identical, including finish times.
4. Add a long-chain test, at least a million vertices, so the regression cannot return.
5. Audit any existing iterative DFS: if it marks on push or pushes all neighbours, check that its callers only need reachability.
6. For SCC, bridges or articulation points, port the after-child step to the frame pop, as in the Tarjan code.