Depth-First Search
Medium+80 XPExplore a graph by going deep down one path before backtracking.
No visualization loaded.
Watch
—
Press Run to begin.
Depth-First Search explores a graph by committing to one path and following it as far as it goes before turning back. It's how you'd solve a maze: pick a direction, keep going until you hit a dead end, then back up to the last fork and try a different way. Where BFS spreads out in rings, DFS plunges deep first — and it uses a stack (last-in-first-out) to remember where to backtrack to.
▸What does 'backtrack' mean?
When the current path dead-ends (no unvisited neighbours left), you step back to the most recent node that still has an unexplored option, and try that. That 'undo my last move and try another' is backtracking — and it's why DFS pairs with a stack, which hands back the most recent node first.
▸Why a STACK for DFS but a QUEUE for BFS?
A stack is last-in-first-out, so it always continues from the node you JUST reached — that's what drives you deeper down one path. A queue is first-in-first-out, so it returns to the oldest waiting node — that's what keeps BFS spreading evenly. The container choice literally is the difference between the two searches.
▸Is DFS the same as recursion?
Closely. DFS is naturally recursive: 'visit me, then DFS each unvisited neighbour.' The call stack from the recursion lesson IS the stack doing the backtracking for you. You can also write it with an explicit stack and a loop — same traversal, just the stack made visible.
▸When DFS vs BFS?
DFS when you need to explore whole paths or 'does any path exist?' — maze solving, detecting cycles, exploring all possibilities. BFS when you need the SHORTEST path in steps. Same graph, same 'visited' bookkeeping, same O(nodes + edges) cost — they just differ in the order they uncover nodes.
How the work grows
O(nodes + edges) is fair — grows in step with the data. Like BFS, each node is visited once and each edge examined once, so time grows in a straight line with the graph. Space is the stack of nodes to backtrack to plus the visited set.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.