Depth-first search plunges down one path as far as it can before backing up. You pick a start, mark it visited, then move to an unvisited neighbor and repeat. When a vertex has no unvisited neighbors left, you backtrack to the previous one and try its other branches.
You can drive this with explicit recursion or with a stack.
function dfs(v, seen) {
seen.add(v);
for (const n of neighbors(v))
if (!seen.has(n)) dfs(n, seen); // recurse deeper
}
The visited set stops you from looping forever on cycles. Every vertex and edge is touched once, so DFS also runs in O(V + E) time.
The deep-first order is what makes DFS natural for whole-graph questions: detecting cycles, finding connected components, and producing a topological order. It reaches the far corners of a structure quickly, which suits problems about global shape rather than nearest distance.
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Why there's no diagram: “”
The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓
The diagram below the answer is the concept . Jump to it ↓