Motivation

DFS explores a graph by committing to a path and following it as far as it goes, then backtracking to the last vertex with an unexplored neighbor.

Why learn DFS?

• Fundamental: it underlies cycle detection, topological sorting, connected components, and many other algorithms.
• Simple and cheap: it runs in O(V + E) time using a stack (or recursion) and a visited marker.
• Versatile: the same traversal answers questions like "are these two vertices connected?" and "how many separate pieces does the graph have?"

To keep results predictable, we always visit a vertex's neighbors in ascending order.