Depth-First Search

How it works, step by step

1. 1

   Start at a node. Mark it visited and give it discovery number 1.

2. 2

   Look at its neighbours in order. Go to the first unvisited one right away - do not finish the list first.

3. 3

   Repeat from the new node: always go deeper while any unvisited neighbour exists. The path you are standing on is the stack.

4. 4

   An edge that leads to a node already on the stack is a back edge - it closes a cycle. Note it, but do not walk it.

5. 5

   No unvisited neighbours left? Backtrack: pop the stack, step back one node, and try its next neighbour.

6. 6

   When you pop the start node, you are done. Every node and edge is handled once - O(V + E).

The code, in JavaScript

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

  function explore(node) {
    visited.add(node);          // mark BEFORE recursing, or a cycle loops forever
    order.push(node);
    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        explore(next);          // go deeper NOW - the rest of the list waits
      }
    }
  }                             // returning from explore() = backtracking

  explore(start);
  return order;
}

const graph = {
  A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F", "G"],
  D: ["B", "H"], E: ["B", "H"], F: ["C"], G: ["C"], H: ["D", "E"],
};

dfs(graph, "A");   // → ["A", "B", "D", "H", "E", "C", "F", "G"]

Dry run: DFS from node A

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Recursive DFS overflows the call stack on deep graphs - in most JavaScript engines somewhere around 10k frames. A path-shaped graph (a long chain, one maze corridor) is enough to crash it. Production DFS on unknown input should be iterative.
• The iterative version visits neighbours in reverse order compared to the recursive one, because a stack flips what you push. Same nodes visited, different order - push the neighbour list reversed if the order must match.
• For cycle detection in a directed graph, one `visited` set is wrong: it mixes up "on my current path" with "finished long ago", and only an edge back to the current path proves a cycle. When you mark matters too - gray goes on when you enter a node, black only when you leave it.
• DFS does not find shortest paths, but people reach for it out of habit. The first path it finds depends on neighbour order and can be absurdly long. "Fewest steps" questions are BFS questions, every time.

Depth-First Search vs. its closest relatives