depth-first search

Depth-first search (DFS) explores a graph by plunging as deep as possible down one path before backing up. It is how you would solve a maze on paper: follow a corridor to its end, and only when you hit a dead end do you retreat to the last junction and try a different turn. DFS commits to a branch fully, then backtracks.

Its natural engine is a stack (last in, first out) — and the simplest way to get a stack is recursion, which uses the program's own call stack. From a vertex you mark it visited, then recurse into the first unvisited neighbor, and into that one's first unvisited neighbor, and so on; when a vertex has no unvisited neighbors left, the recursion returns (backtracks) to the previous vertex. As with BFS, marking visited vertices is what stops cycles from looping forever. You can also write DFS iteratively with an explicit std::stack.

DFS also visits each vertex once and each edge once, giving O(V + E) time on an adjacency list. It does not find shortest paths, but its deep, finish-this-branch order is perfect for tasks like detecting cycles, finding connected components, exploring all configurations, and producing a topological sort of a directed acyclic graph.