What does the stack do in DFS on graphs?

AlgorithmsJunior~2 min read

Short answer

The stack in DFS holds the current path and the state of the vertices we have entered but not yet fully explored. Because of the LIFO principle the stack drives both the descent and the backtracking: as soon as a vertex runs out of unvisited neighbors, it is popped off the stack and the algorithm returns to the previous vertex. In the recursive version, the call stack plays the role of this stack.

Detailed answer

Why the stack is needed in DFS

Controls the traversal order (LIFO): the last one added is the first one visited, which is why the algorithm goes "deep".
Holds the context of a vertex: the vertex itself and, if needed, the index of the next neighbor to process.
Provides backtracking: once the current vertex has no more unvisited neighbors, we "exit" it and return to its parent.
Allows writing an iterative (non-recursive) DFS (important for large graphs, to avoid overflowing the call stack).

What exactly is on the stack

Simple version: just the vertex. Works if we only need the order of "entering" vertices.
Extended version (a frame): { v, i } - the vertex v and the index i of the next neighbor. This mimics recursion and lets you handle "enter/exit" events.
Sometimes the parent, entry/exit time, vertex color, and so on are also stored, if the task requires it.

Iterative DFS with a stack (JS)

Simple traversal: mark a vertex visited when it is pushed onto the stack, to avoid pushing duplicates.

function dfsIterative(adj, start) {
  const n = adj.length;
  const visited = new Array(n).fill(false);
  const order = [];
  const stack = [start];
  visited[start] = true; // mark on push

  while (stack.length) {
    const v = stack.pop();
    order.push(v); // vertex-enter event

    // To keep the order stable left-to-right, push neighbors in reverse order
    for (let i = adj[v].length - 1; i >= 0; i--) {
      const u = adj[v][i];
      if (!visited[u]) {
        visited[u] = true;
        stack.push(u);
      }
    }
  }

  return order;
}

// Example
const adj = [
  [1, 2], // 0
  [3],    // 1
  [3],    // 2
  []      // 3
];
console.log(dfsIterative(adj, 0)); // [0, 1, 3, 2]

Traversal with enter/exit events (frames mimic the recursion call stack):

function dfsWithEvents(adj, start, onEnter, onExit) {
  const n = adj.length;
  const visited = new Array(n).fill(false);
  const stack = [{ v: start, i: 0, entered: false }];
  visited[start] = true;

  while (stack.length) {
    const top = stack[stack.length - 1];

    if (!top.entered) {
      if (onEnter) onEnter(top.v);
      top.entered = true; // enter event handled
    }

    if (top.i < adj[top.v].length) {
      const u = adj[top.v][top.i++];
      if (!visited[u]) {
        visited[u] = true;
        stack.push({ v: u, i: 0, entered: false });
      }
    } else {
      if (onExit) onExit(top.v); // exit event
      stack.pop();
    }
  }
}

// Example usage
const enter = (v) => console.log('enter', v);
const exit = (v) => console.log('exit', v);
dfsWithEvents([[1,2],[3],[3],[]], 0, enter, exit);

Recursive DFS: the call stack does the same thing

function dfsRecursive(adj, start) {
  const n = adj.length;
  const visited = new Array(n).fill(false);
  const order = [];

  function rec(v) {
    visited[v] = true;           // analogous to: pushing a frame
    order.push(v);               // enter event
    for (const u of adj[v]) {
      if (!visited[u]) rec(u);
    }
    // exit event happens here (before returning)
  }

  rec(start);
  return order;
}

Complexity and practical details

Time: O(V + E), each vertex and edge is considered a bounded number of times.
Memory: O(V), the stack depth in the worst case equals the length of the path.
Neighbor order affects traversal order. To keep it deterministic, neighbors are most often sorted and pushed in reverse order.
In an undirected graph, checking visited is enough; storing parent is needed if you distinguish tree edges from back edges (for example, to detect cycles).

Frequent mistakes in an interview

Marking a vertex visited only on pop instead of on push, which leads to multiple copies of the vertex on the stack.
Forgetting to pop the vertex off the stack after processing all its neighbors in the frame-based version.
Not reinitializing visited between DFS runs for different components of the graph.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.