Depth-first search
From each node, go straight to the first neighbour not yet visited, and keep going. When a node has nothing new left, back up to the node before it and try that one's next neighbour. The call stack is exactly the path from the start to where you are.
call stack: the path from the start to here
Explore from A, always going deeper before going wider.
1function dfs(adj, u, seen, order) {2 seen[u] = true;3 order.push(u);4 for (const v of adj[u]) {5 if (!seen[v]) dfs(adj, v, seen, order);6 }7}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | V + E | every reachable node and edge is looked at once |
| average | V + E | any graph |
| worst | V + E | the same for every graph |
| space | V | the call stack can hold every node on a long path |
Where it breaks
- It does not find shortest paths. Pick A long path: DFS reaches F after going round the whole ring, five steps, though F is right next to A. Use breadth-first search for the fewest hops.
- Deep graphs overflow the stack. Each step deeper is one more waiting call. On a path of a million nodes, recursion crashes; an explicit stack in a loop does not.
- What it is good for. Finding whether two nodes connect, detecting cycles, ordering tasks and exploring mazes. All of them only need to reach everything, not to reach it by the shortest route.