Depth-first search, or DFS, explores a graph by committing to one path and following it as far as it will go before backing up. From the current node it picks an unvisited neighbor, moves there, and repeats; only when a node has no unvisited neighbors left does it backtrack to the most recent choice point and try a different branch. This last-in, first-out behavior is naturally expressed with a stack, or, more commonly, with recursion, where the call stack plays the role of the explicit stack.
Like breadth-first search, DFS visits each node once and examines each edge a constant number of times, so it runs in time proportional to V plus E, the number of vertices plus edges. The MIT 6.006 lecture on depth-first search presents it together with two of its most important uses: detecting whether a directed graph contains a cycle, and producing a topological ordering of a directed acyclic graph by recording the order in which nodes finish.
DFS is far more than a way to visit every node. By tracking when each node is first entered and when it is finished, the search reveals deep structure in the graph: which edges form the tree of the search, which point back to an ancestor (revealing a cycle), and how the graph decomposes into strongly connected components. Robert Tarjan’s 1972 paper, “Depth-First Search and Linear Graph Algorithms,” made this precise, showing how a single depth-first pass could find the strongly connected components of a directed graph and the biconnected components of an undirected graph in linear time. Tarjan’s framing of depth-first search as backtracking established it as a general-purpose technique rather than a one-off trick.
The contrast with breadth-first search is instructive. Both run in O(V+E) and share the same outer loop; they differ only in the data structure that decides which node to explore next. A queue gives the breadth-first, level-by-level sweep that finds shortest paths; a stack gives the depth-first plunge that exposes cycles, orderings, and connectivity. Choosing between them is choosing what you want to learn about the graph.