Iterative Depth-First Search Without Losing Finish Times

Depth-first search is the traversal most often written recursively and most often rewritten iteratively after a stack overflow. The rewrite looks mechanical — replace the call stack with an array — and the naive version is wrong in a way that usually goes unnoticed: it visits vertices in an order that is not depth-first, and it produces no finish times at all. Both defects disappear once the stack holds frames rather than vertices, but the frame has to carry more state than the recursion appears to need.

Why pushing all children is not DFS

The tempting translation pushes every neighbour of the current vertex and pops one at a time:

def dfs_wrong(adj, s):
    seen, stack, order = set(), [s], []
    while stack:
        u = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                stack.append(v)
    return order

On a path this coincides with recursive DFS. On a graph with a vertex of degree k it does not: all k neighbours are pushed at once, and the last one popped is explored to completion before the second-to-last is even looked at. Meanwhile the first neighbour sits at the bottom of the stack, and any vertex reachable from it is discovered only after the other k−1 subtrees are finished. The result is a traversal whose order depends on the order neighbours were pushed, and which explores one branch deeply while holding k−1 pending siblings — the opposite of the recursion’s behaviour, where only the current path is pending.

The defect is not cosmetic. Finish times computed from this order are wrong, and every algorithm that depends on them inherits the error. Topological sorting by reverse finish order produces invalid orderings on graphs where the two traversals differ, and the failure is silent because the output still looks like a permutation of the vertices.

The frame the recursion actually keeps

A recursive call’s state at any moment is a pair: which vertex it is visiting, and which of that vertex’s outgoing edges it has already examined. On return from a child, the call resumes at the next edge. That index is invisible in source code because the language’s call machinery stores it in the instruction pointer, but it is the entire difference between a correct iterative DFS and the version above.

An explicit frame is a vertex plus a cursor into its adjacency list. The loop looks at the top frame, advances its cursor to the next unexamined edge, and either pushes a new frame for a white neighbour or pops the frame when the cursor is exhausted — recording the finish time at that moment.

def dfs_iterative(adj):
    n = len(adj)
    color = [0] * n            # 0 white, 1 grey, 2 black
    d = [0] * n
    f = [0] * n
    t = 0
    stack = []                 # list of [vertex, next_edge_index]

    for root in range(n):
        if color[root] != 0:
            continue
        color[root] = 1
        t += 1
        d[root] = t
        stack.append([root, 0])
        while stack:
            u, i = stack[-1]
            if i < len(adj[u]):
                v = adj[u][i]
                stack[-1][1] = i + 1        # advance before descending
                if color[v] == 0:
                    color[v] = 1
                    t += 1
                    d[v] = t
                    stack.append([v, 0])
            else:
                color[u] = 2
                t += 1
                f[u] = t
                stack.pop()
    return d, f

Two details carry the semantics. The cursor advances before the descent, so that when the child finishes and the parent frame is on top again, the parent resumes at the edge after the one that led to the child. And the finish time is written at the pop, which is the only point at which the vertex’s entire subtree is known to be complete. Skipping either detail produces a traversal that looks plausible and fails on the interval nesting property that timestamps are supposed to guarantee.

The memory cost is now explicit: one frame per vertex on the current path, each holding a vertex identifier and an index. That is comparable to the recursion’s frame in size and identical in growth, but it lives on the heap and can be sized, spilled, or bounded. On a chain of a million vertices the recursion overflows a thread stack; the explicit version allocates a million small frames on the heap and succeeds, at a cost proportional to the size of a frame.

What the explicit stack buys

The reason to prefer the iterative form is not portability alone. Three capabilities appear once the traversal state is data.

Pausing. A generator or coroutine that yields each newly discovered vertex can be implemented directly: the stack survives between yields, and resumption continues from the exact frame. The recursive equivalent requires a language with coroutines or a continuation capture.

Bounding. The traversal can refuse to descend beyond a depth limit, which turns it into a depth-limited search. The check is a comparison against the stack length, whereas in the recursive version it is a parameter the caller must thread through every call.

Interleaving. Several searches can advance in lockstep by keeping one stack each and stepping them round-robin. Recursive implementations cannot do this without threads, and threads bring their own stacks and synchronization.

The cost is that every algorithm expressed recursively must be re-expressed. The bookkeeping that the compiler performed — where to resume, what to do on return — becomes code the programmer writes, and the correctness argument becomes an argument about the frame layout rather than about the recursion.

Post-order without a second stack

Iterative post-order traversal has a standard trick: push a vertex, then push a marker, then its children, and treat the marker as “now finish the vertex above it”. A marker-based version of DFS keeps a separate boolean per stack entry and treats a re-popped entry as finished.

def dfs_with_markers(adj, s):
    seen, stack = set(), [(s, False)]
    entered, finished = [], []
    while stack:
        u, expanded = stack.pop()
        if expanded:
            finished.append(u)          # post-order position
            continue
        if u in seen:                   # guard against re-entry on cycles
            continue
        seen.add(u)
        entered.append(u)               # pre-order position
        stack.append((u, True))         # finish u after its children
        for v in adj[u]:
            stack.append((v, False))

This visits children in reverse push order — the last neighbour pushed is the first explored — and produces the correct pre-order together with a valid post-order, using only one stack. The trade against the frame version is that the stack can grow to O(m) entries rather than O(n): every edge to a white vertex pushes an entry, and the marker doubles the count. For dense graphs the frame formulation is smaller; for sparse graphs the difference is a constant factor.

The marker version also cannot distinguish a cross edge from a forward edge during inspection, because it does not maintain grey state at the moment of edge examination. Any algorithm needing the four-class edge taxonomy needs the frame version with colours.

The neighbour-order trap

A subtle property of the recursive algorithm is that the order in which a vertex’s neighbours are explored is fixed by the adjacency list, and reversing the list reverses the subtree order without changing the set of tree edges on a tree. Iterative implementations that push neighbours in list order effectively reverse it, because the last pushed is the first popped. Two implementations that agree on the recursive version will disagree on which tree they produce, and on a graph with multiple valid topological orders they will emit different valid answers — a discrepancy that shows up as nondeterminism in test suites rather than as an error.

The fix is either to push in reverse order or to use the frame formulation, which descends immediately into the first unexamined neighbour and therefore matches the recursion exactly. When comparing two implementations, comparing the resulting forest rather than only the vertex order is the reliable check.

Memory layout and the cost of small frames

An explicit stack of Python tuples allocates one object per frame and grows a list; a million frames means a million objects, which a generational collector must trace. A C implementation uses a flat array of two-element structs and reallocs geometrically, which is the same amortized growth argument as a dynamic array and touches contiguous memory. The algorithmic complexity is identical — O(n + m) time, O(n) space — but the constant factor and the pressure on the allocator differ by a large margin, which is why graph libraries in systems languages use the flat array form even when the recursive version would fit the stack.

The boundary case worth testing is a graph that is a single long chain with the vertices numbered in reverse. The traversal then reaches maximum depth before any vertex finishes, so the stack is at its largest exactly when memory pressure is highest, and a frame implementation with a fixed capacity overflows there rather than anywhere else.