Mathwords logoMathwords

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 G=(V,E)G = (V, E) and a start vertex ss, DFS calls a procedure DFS(v)\text{DFS}(v) that marks vv as visited and then, for each neighbor ww of vv in a fixed order, calls DFS(w)\text{DFS}(w) if ww is unmarked. An explicit last-in, first-out stack can replace the recursion. DFS(s)\text{DFS}(s) visits exactly the vertices reachable from ss; 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

T=O(∣V∣+∣E∣)T = O(|V| + |E|)
Where:
  • TT = Running time of DFS on a graph stored as adjacency lists
  • ∣V∣|V| = Number of vertices, each marked and visited once
  • ∣E∣|E| = 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.
A→B→D(dead end, back to B)A \to B \to D \quad (\text{dead end, back 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.
B→E→F→CB \to E \to F \to C
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.
6−1=5 tree edges,6−5=1 back edge6 - 1 = 5 \text{ tree edges}, \quad 6 - 5 = 1 \text{ back edge}
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.

Related Terms