Depth-First Search

Depth-first search (DFS) is the opposite instinct to BFS: instead of spreading out evenly, it commits to one path and follows it as far as it can go, only backing up to the last fork when it dead-ends. It doesn't find shortest paths, but it's the natural tool for visiting every corner of a graph, detecting cycles, and ordering dependencies.

A stack drives it deep

Where BFS uses a FIFO queue, DFS uses a stack — last in, first out. Following the *most recently discovered* node is what sends the search plunging downward before it ever goes wide. In practice you rarely write the stack yourself: recursion uses the program's own call stack for free, and each return *is* a backtrack to the previous fork.

1. 1Start at a node and mark it visited.
2. 2Pick any unvisited neighbour and recurse into it — go deep.
3. 3When a node has no unvisited neighbours left, backtrack: return to the node that called it.
4. 4Continue until every node reachable from the start has been visited.

function dfs(graph, start) {
  const visited = new Set();
  (function visit(u) {
    visited.add(u);               // mark on entry
    for (const v of graph[u]) {
      if (!visited.has(v)) visit(v); // dive deeper, then backtrack on return
    }
  })(start);
  return visited;
}