Depth-First Search Visualizer

Depth-first search commits. It picks a direction, follows it as far as it goes, and only when it can go no further does it back up and try the road not taken. Where breadth-first search is cautious and systematic, DFS is the algorithm equivalent of walking into a maze and always turning left.

That single behaviour makes it the foundation of a surprising amount of computer science. Cycle detection, topological sorting, strongly connected components, articulation points, maze generation, and every backtracking solver you have ever written are all DFS with different bookkeeping attached. It is less a search algorithm than a way of imposing structure on a graph.

What is depth-first search?

DFS explores a graph by going as deep as possible along each branch before backtracking. From the current node it picks an unvisited neighbour and moves there immediately, repeating until it reaches a node with no unvisited neighbours — a dead end — at which point it retreats to the most recent node that still has options.

It can be written recursively, where the language's call stack does the remembering, or iteratively with an explicit stack. The two are equivalent; the recursive form is shorter and the iterative form is what you need when the graph is deep enough to overflow the call stack.

The visualiser uses the explicit-stack version deliberately. The recursive form's state lives in the call stack, which is invisible — you cannot show a learner a data structure they cannot see. With an explicit stack, the thing driving the traversal is on screen.

Why it works

DFS's correctness claim is weaker than BFS's and worth stating precisely: DFS visits every node reachable from the start, exactly once. It makes no claim about path length, and the path it finds to a node is frequently not the shortest one.

Completeness follows from the stack. Every discovered node is pushed, and the loop continues until the stack is empty, so nothing discovered is ever abandoned. The visited set guarantees each node is processed once, which also guarantees termination on cyclic graphs.

The property that makes DFS powerful is not about reachability at all — it is about timing. Each node has a discovery time (when DFS enters it) and a finish time (when DFS has exhausted its subtree and backs out). The nesting relationship between those intervals encodes the structure of the graph: if u's interval contains v's, then v is a descendant of u in the DFS tree. Topological sorting, cycle classification and strongly connected components are all read off these times rather than off the traversal order.

Step-by-step walkthrough

Same graph as the BFS example: A connects to B and C; B connects to D; C connects to D and E. Start at A, exploring neighbours in alphabetical order.

1. Push A. Pop A and visit it. Push its neighbours: stack is [C, B] (B on top, so B goes first).
2. Pop B and visit it. Push its unvisited neighbour D. Stack: [C, D].
3. Pop D and visit it. Its neighbours B and C — B is visited, C is already on the stack. Stack: [C].
4. Pop C and visit it. Push its unvisited neighbour E. Stack: [E].
5. Pop E and visit it. No unvisited neighbours. Stack empty; traversal ends. Order: A, B, D, C, E.
6. Compare with BFS on the same graph, which gave A, B, C, D, E. DFS reached D at step three, via A→B→D; BFS reached it last. Neither is wrong — they are answering different questions.

What DFS is really for

Using DFS to find a path between two nodes works, but it is the least interesting thing it does — and the path it returns may be far from shortest. The real uses come from the discovery and finish times.

Cycle detection. In a directed graph, an edge to a grey node — one currently on the recursion path — is a back edge and proves a cycle exists. This is how build systems detect circular dependencies and how type checkers catch recursive type definitions.

Topological sorting. Push each node onto a list when it *finishes*, then reverse the list. The result orders every node before all of its dependents. This is the algorithm behind build ordering, task scheduling with prerequisites, and spreadsheet recalculation.

Connected components. Run DFS from each unvisited node in turn; each run marks exactly one component. This is O(V + E) for the whole graph and is how flood fill, island counting and clustering problems are solved.

Backtracking. Sudoku solvers, n-queens, maze generation and constraint satisfaction are DFS over an implicit graph of partial solutions, where 'backtrack' means undoing the last decision. The graph is never built; it is explored as it is generated.

Strongly connected components via Tarjan's or Kosaraju's algorithm, and articulation points and bridges — the nodes and edges whose removal disconnects a network — are all DFS with extra bookkeeping on the timing information.

How the animation above works

Watch the stack panel rather than the graph. Nodes enter and leave from the same end, and the traversal repeatedly dives to a dead end before the stack shortens and a different branch begins. That saw-tooth pattern — deepen, deepen, deepen, retreat — is the signature of depth-first exploration.

Run BFS and DFS on the same graph from the same start and compare the visited-order panels. BFS's order fans out evenly; DFS's snakes. Then set a destination node: DFS will often find a path with noticeably more edges than BFS's, which is the clearest demonstration that DFS makes no shortest-path guarantee.

Time and space complexity

O(V + E) time with an adjacency list — identical to BFS, and for the same reason. Every vertex is processed once, and every edge is examined once from each endpoint. With an adjacency matrix it becomes O(V²).

O(V) space in the worst case for the visited set, plus the stack. The important practical difference from BFS is the *shape* of that stack usage: DFS's stack holds the current path, so it is O(depth), while BFS's queue holds an entire level, which can be O(V) on a branching graph.

On a wide, shallow graph DFS uses dramatically less memory than BFS. On a deep, narrow one — a long chain — DFS's stack reaches O(V) and the recursive form risks a stack overflow. This is the main reason to prefer the iterative version for graphs of unknown shape.

Recursive or iterative?

The recursive form is shorter, reads closer to the definition, and gives you finish times for free — the code after the recursive call runs exactly when the node finishes. For topological sorting and cycle detection this matters, because those algorithms are naturally expressed in terms of finish times.

The iterative form has no depth limit. Python defaults to a recursion limit around 1,000, and a graph of ten thousand chained nodes will crash a recursive DFS long before it runs out of memory. Java and JavaScript fail similarly at a few thousand frames.

One subtlety catches people out: the iterative version pushes neighbours in reverse order to match the recursive version's traversal sequence, because the last one pushed is the first one popped. Neither order is more correct, but if you are comparing outputs between implementations, this is usually why they differ.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Depth-First Search in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * DFS, both forms. They visit the same nodes; the iterative version pushes
 * neighbours reversed so the traversal ORDER matches the recursive one.
 */
function dfsRecursive(graph, node, visited = new Set(), order = []) {
  visited.add(node);
  order.push(node);

  for (const neighbour of graph.get(node) ?? []) {
    if (!visited.has(neighbour)) {
      dfsRecursive(graph, neighbour, visited, order);
    }
  }

  return order;
}

function dfsIterative(graph, start) {
  const visited = new Set();
  const order = [];
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();
    // A node can be pushed several times before it is popped, so re-check.
    if (visited.has(node)) continue;

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

    const neighbours = [...(graph.get(node) ?? [])].reverse();
    for (const neighbour of neighbours) {
      if (!visited.has(neighbour)) stack.push(neighbour);
    }
  }

  return order;
}

const graph = new Map([
  ["A", ["B", "C"]],
  ["B", ["A", "D"]],
  ["C", ["A", "D", "E"]],
  ["D", ["B", "C"]],
  ["E", ["C"]],
]);

console.log(dfsRecursive(graph, "A")); // ["A", "B", "D", "C", "E"]
console.log(dfsIterative(graph, "A")); // ["A", "B", "D", "C", "E"]

Advantages and disadvantages

Real-world applications

• Topological sorting for build systems, task schedulers, dependency resolution and spreadsheet recalculation.
• Cycle detection — circular imports, circular dependencies in package managers, and deadlock detection in resource graphs.
• Finding connected components, flood fill, island counting and image segmentation.
• Backtracking solvers: sudoku, n-queens, maze generation, crossword filling and constraint satisfaction generally.
• Tarjan's and Kosaraju's algorithms for strongly connected components, used in compiler optimisation and social network analysis.
• Finding articulation points and bridges — the nodes and links whose failure would disconnect a network.
• Tree and expression traversals: pre-order, in-order and post-order are all DFS with the processing step in different places.
• Garbage collection mark phases, which trace reachable objects depth-first from the roots.

Interview questions

The questions that actually get asked about Depth-First Search, with the answers an interviewer is listening for.

1. Q1. Why does DFS not find the shortest path?

   Because it commits to a branch and follows it to the end before considering alternatives. The first time it reaches a node is via whatever route it happened to take, not the shortest one — a node two edges away might be found after a twenty-edge detour. BFS gets the guarantee because it explores strictly in order of increasing distance; DFS explores in order of most-recently-discovered.

2. Q2. How do you detect a cycle in a directed graph with DFS?

   Use three states rather than a visited flag: white for undiscovered, grey for nodes on the current recursion path, and black for fully finished nodes. An edge to a grey node is a back edge and proves a cycle. A visited set alone cannot distinguish that from a cross edge to an already-finished branch, which is harmless — that distinction is exactly what the grey state provides.

3. Q3. How does DFS produce a topological sort?

   Append each node to a list when it *finishes* — after all its descendants are done — then reverse the list. A node finishes only once everything it points to has finished, so reversing the finish order puts every node before its dependents. The same traversal also detects cycles, which is important because a cyclic graph has no valid topological order at all.

4. Q4. When would you choose iterative DFS over recursive?

   When the graph might be deep. Recursion depth is bounded by the language runtime — around 1,000 frames in Python by default, a few thousand in Java and JavaScript — so a long chain crashes a recursive implementation. The iterative version uses heap memory for its stack and is limited only by available memory. The trade is that finish times are less convenient to capture iteratively.

5. Q5. What is the difference in memory usage between BFS and DFS?

   DFS's stack holds the current path, so it is O(depth). BFS's queue holds an entire level, so it is O(width), which on a branching graph can approach O(V). On a wide shallow graph DFS uses far less memory; on a long chain the two converge, since the path is the whole graph.

Common mistakes

• Using a two-state visited set for directed cycle detection, which reports cycles where only harmless cross edges exist.
• Failing to re-check visited after popping in the iterative version — a node can be pushed several times before it is first popped.
• Marking nodes visited when pushing rather than when popping in the iterative form, which skips nodes that should be explored via a different branch in some variants.
• Using recursive DFS on graphs of unknown depth and hitting a stack overflow in production on data that worked in testing.
• Recording the topological order on entry rather than on finish, which produces an order that looks plausible and is wrong.
• Forgetting that a full traversal of a disconnected graph needs an outer loop over all unvisited nodes, not one DFS call.
• Expecting DFS to return a shortest path, which it makes no promise about.

Optimisation tips

• Prefer the iterative form when the graph's depth is unknown or user-controlled — it removes an entire class of production failure.
• For cycle detection and topological sort, keep the recursive form if depth allows: finish times fall out naturally from the code position after the loop.
• Use an explicit colour array rather than two separate sets; it is one lookup instead of two and makes the three states obvious.
• For grid problems, index cells into a flat array rather than hashing coordinate pairs — the constant-factor difference is substantial.
• In backtracking, undo the state change immediately after the recursive call returns rather than copying state into each branch; copying is what makes naive backtracking slow.
• Prune aggressively in backtracking searches — checking feasibility before recursing eliminates entire subtrees, and that dominates any micro-optimisation of the traversal itself.

Summary

Depth-first search follows one branch as far as it goes, then backtracks to the most recent node with unexplored options. It runs in O(V + E) time and uses O(depth) memory, which makes it much cheaper than BFS on wide graphs and riskier on deep ones, where the recursive form can overflow the call stack.

Its value is not path-finding — it offers no shortest-path guarantee — but structure. The discovery and finish times it produces are what make topological sorting, directed cycle detection, strongly connected components and articulation points possible, and every backtracking solver is DFS over a graph that is generated as it is explored. Learn the traversal, then learn what the finish times tell you; the second part is where the algorithm earns its place.

Frequently asked questions

Related algorithms

• Breadth-First Search

  Explore a graph level by level with a queue — the shortest path on unweighted edges.

  O(V + E)Intermediate

• Kruskal's Algorithm

  Sort every edge by weight and add the cheap ones that don't close a cycle.

  O(E log E)Advanced

• Dijkstra's Algorithm

  Greedily settle the nearest unvisited node to get shortest paths on non-negative weights.

  O((V + E) log V)Advanced