DFS (Depth-First) Visualization — Step by Step

A stack drives everything

DFS commits to one branch and follows it as deep as it can go before backing up — and that behaviour comes entirely from using a LIFO [stack](/workspace/stack). The most recently discovered node is processed first, so the traversal keeps extending its newest path instead of returning to older discoveries. Recursion gives you the same thing implicitly: the call stack *is* the stack. This visualizer uses the explicit iterative form — push the start node, then loop: pop, visit, push unvisited neighbours. Swap the stack for a queue and the same loop becomes BFS.

A concrete trace

Use the graph with edges 0–1, 0–4, 1–2, 1–3, and 3–4, starting at 0. Push 0 → stack [0]. Pop 0, visit, push neighbours 4 then 1 (reversed, so 1 ends on top) → [4, 1]. Pop 1, visit, push 3 then 2 → [4, 3, 2]. Pop 2, visit — dead end, its only neighbour 1 is visited. Pop 3, visit, push its unvisited neighbour 4 → [4, 4]. Pop 4, visit. The leftover 4 is popped and skipped. Visit order: 0, 1, 2, 3, 4 — one deep dive, not expanding rings.

Backtracking is just popping

Watch what happened at node 2: it had no unvisited neighbours, so the dive was stuck. DFS "backtracks" — but no special code exists for that. The next pop simply yields node 3, which was pushed while visiting node 1, so the traversal naturally resumes from the deepest point that still has unexplored options. That is the elegance of the stack formulation: the stack *remembers* every branch point for you. In the recursive version the same thing appears as a function call returning to its caller and the loop over neighbours continuing.

Same graph, opposite order to BFS

Run BFS on the identical graph and it visits 0, 1, 4, 2, 3 — both of 0's neighbours before anything deeper. DFS instead reached node 4 *last*, through the long path via 3, even though 4 sits one edge from the start. This is the crucial caveat: DFS says nothing about shortest paths. The route it finds to a node can be arbitrarily longer than the best one. What DFS gives you instead is deep structural information — discovery order, dead ends, and back edges — which is exactly what cycle detection and topological sorting need.

Duplicates on the stack are fine

In the trace, node 4 appeared on the stack twice: once pushed from 0, once from 3. That is normal for iterative DFS — a node may be reachable from several frontier nodes before either copy is popped. Correctness is preserved by checking the visited set *at pop time*: the first copy popped gets visited, later copies are discarded with a continue. The visualizer shows this as pop events on already-visited nodes that cause no state change. Cost stays O(V + E): each edge pushes at most one stack entry, and each vertex is visited once.

JavaScript

function dfs(graph, start) {
  // graph: Map or object mapping node -> array of neighbours
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length > 0) {
    const node = stack.pop(); // LIFO
    if (visited.has(node)) continue; // stale duplicate entry

    visited.add(node);
    order.push(node);

    // Reverse so the first-listed neighbour is explored first
    for (const neighbor of [...graph[node]].reverse()) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
  return order; // nodes in depth-first visit order
}

Python

def dfs(graph, start):
    """Iterative DFS. graph: dict mapping node -> list of neighbours."""
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()  # LIFO
        if node in visited:
            continue  # stale duplicate entry

        visited.add(node)
        order.append(node)

        # reversed() so the first-listed neighbour is explored first
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)

    return order  # nodes in depth-first visit order

Java

import java.util.*;

public class DFS {
    // graph: adjacency list, graph.get(u) = neighbours of u
    public static List<Integer> dfs(List<List<Integer>> graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Deque<Integer> stack = new ArrayDeque<>();
        List<Integer> order = new ArrayList<>();

        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop(); // LIFO
            if (visited.contains(node)) continue; // stale duplicate

            visited.add(node);
            order.add(node);

            // Push in reverse so the first neighbour is explored first
            List<Integer> neighbors = graph.get(node);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int neighbor = neighbors.get(i);
                if (!visited.contains(neighbor)) stack.push(neighbor);
            }
        }
        return order;
    }
}