Iterative DFS — Avoid Stack Overflow

Basic iterative

void dfs(int start, List[] graph) {
  boolean[] visited = new boolean[graph.length];
  Deque stack = new ArrayDeque<>();
  stack.push(start);
  while (!stack.isEmpty()) {
    int u = stack.pop();
    if (visited[u]) continue;
    visited[u] = true;
    for (int v : graph[u]) if (!visited[v]) stack.push(v);
  }
}

Iterator-based state

To maintain 'after all children processed' semantics: stack of iterators, not just vertices. Enables post-order + articulation-point detection.

Simulated call stack

Frame = (vertex, iterator over children, phase). Enter/exit hooks map to recursive call/return.

Complexity

Same O(V+E). Extra: explicit stack space O(V).