Explore a network like a maze: pick a path and follow it as DEEP as it goes; hit a dead end, back up to the last fork, take the next branch. That’s depth-first search — a stack (or recursion) is all it needs, and it’s the backbone of cycle detection, topological sort, connected components, and maze-solving. Its sibling [[the-breadth-first|breadth-first]] fans out in rings; DFS plunges. Slide to plunge down the graph.
Depth-first search explores a graph by going as DEEP as possible before backtracking: from a vertex, recurse into an unvisited neighbor, and only when none remain return to the previous vertex (an explicit stack, or the call stack). It visits every vertex/edge once, O(V+E), and its discovery/finish times and tree/back/forward/cross edge classification power a remarkable amount: cycle detection, [[the-topological-sort|topological sort]], [[the-strongly-connected|strongly-connected components]], [[the-articulation-point|articulation points]], and maze/backtracking search. Its counterpart [[the-breadth-first|BFS]] instead explores in distance rings. A fail-loud self-check throws unless DFS yields the known preorder (deep before wide). ◆ real graph algorithms, node-verified.
DFS finds A path, not the SHORTEST (that’s [[the-breadth-first|BFS]] on unweighted graphs); deep recursion can overflow the stack on huge graphs (use an explicit one). The traversal order and O(V+E) cost are exact.