Depth-First Search — Definition, Formula & Example
Depth-first search (DFS) is a way to visit every vertex reachable from a starting vertex by following one path as far as it goes, then backing up to the most recent vertex that still has an unvisited neighbor and trying a new branch.
Given a graph and a start vertex , DFS calls a procedure that marks as visited and then, for each neighbor of in a fixed order, calls if is unmarked. An explicit last-in, first-out stack can replace the recursion. visits exactly the vertices reachable from ; to cover a disconnected graph, restart from each unvisited vertex. The edges used to reach new vertices form a DFS tree (a DFS forest after restarts). In an undirected graph, every non-tree edge joins a vertex to one of its ancestors in its tree.
Key Formula
Where:
- = Running time of DFS on a graph stored as adjacency lists
- = Number of vertices, each marked and visited once
- = Number of edges. Each edge is examined a constant number of times (twice in an undirected graph).
Worked Example
Problem: A graph has vertices A, B, C, D, E, F and 6 edges: A–B, A–C, B–D, B–E, C–F, E–F. Run DFS from A, checking neighbors in alphabetical order. Find the visit order and the DFS tree.
Step 1: Start at A and keep moving to the first unvisited neighbor. D's only neighbor is B, which is already visited. D is a dead end, so you backtrack to B.
Step 2: From B, the next unvisited neighbor is E. From E go to F, and from F go to C. Both of C's neighbors, A and F, are visited, so you backtrack through F, E, B, and A. A's remaining neighbor C is already visited, so the search ends.
Step 3: Each newly visited vertex adds one tree edge, so the 6 vertices give 5 tree edges. The one leftover edge, A–C, joins C back to its ancestor A. This back edge shows the graph contains the cycle A–B–E–F–C–A.
Answer: The visit order is A, B, D, E, F, C. The DFS tree has edges A–B, B–D, B–E, E–F, F–C. Edge A–C is the single back edge.
Why It Matters
DFS is a core algorithm in a college data structures course (often called CS2) and in discrete math. It powers topological sorting, which orders courses so that every prerequisite comes first. It also drives maze solvers, finds connected components, and detects cycles in dependency graphs.
Common Mistakes
Mistake: Visiting all of the start vertex's neighbors before going deeper, which gives A, B, C, D, E, F in the example above.
Correction: That order comes from breadth-first search, which uses a queue. DFS uses a stack, so it always follows the most recently discovered vertex first. That is why D is visited before C.
