FoundationSource checked

Depth-First Search

Explores a graph by following one path as far as possible before backtracking.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Beginner
Family: Graph Traversal
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 14
Code example: Ready
Visualization: Ready
Aliases: DFS

Overview

Depth-First Search uses recursion or an explicit stack to visit a node, continue to an unvisited neighbor, and backtrack when no unexplored neighbors remain.

Core Concepts

stack frontierbacktrackingvisited setentry and exit times

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(V + E)

Average

O(V + E)

Worst

O(V + E)

Space

O(V)

When to Use

Use it for reachability, cycle checks, topological ordering, and component discovery.
Use it when backtracking or recursive structure matches the problem.
Use it when memory should track a path rather than a full BFS frontier.

When Not to Use

Avoid it when shortest paths in an unweighted graph are required.
Avoid recursive DFS on very deep graphs without stack-depth safeguards.
Avoid it when traversal order must be level by level.

What It Does

Visits nodes by going deep first
Backtracks when no unvisited neighbor remains

Use Cases

Detecting cycles
Topological sorting
Solving mazes

Inputs

Graph
Starting node

Outputs

Traversal order
Discovery and finish information
Reachability information

Pseudocode

1.Start at a node
2.Mark the node as visited
3.Visit one unvisited neighbor recursively
4.Backtrack when all neighbors are visited
5.Continue until all reachable nodes are visited

Canonical Example

Input: graph = {A: [B, C], B: [D], C: [], D: []}, start = A
Output: visited = [A, B, C, D]
Explanation: Depth-First Search: The traversal starts at A and visits reachable nodes by following edges.

Implementation Notes

Use color states or entry/exit markers when cycle type matters.
Use an explicit stack for very deep or user-supplied graphs.
Keep neighbor ordering deterministic if tests depend on traversal order.

Common Pitfalls

Forgetting visited-state tracking in graphs with cycles.
Confusing discovery order with shortest-path order.
Letting recursive implementations overflow the call stack.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show the active path extending and then backtracking.

Step 1 of 5: Start at a node

graph-depth

Notes

DFS is a traversal pattern behind many graph algorithms, including topological sort and strongly connected components.

Sources (1)

What each reference supports for this entry.

CLRS

Book

Textbook reference for the algorithmic family and analysis of Depth-First Search.

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

Has variantsIterative Deepening DFS

Graph Traversal · Core

Iterative deepening DFS repeats depth-limited DFS with increasing search limits.

Compare with this

Used byBiconnected Components

Graph Traversal · Core

DFS discovery and lowlink values drive the decomposition.

Compare with this

Used byBridge Detection

Graph Traversal · Core

Bridge detection uses DFS discovery and low-link values to find edges whose removal disconnects a graph.

Compare with this

Used byConstraint Satisfaction Backtracking

Optimization · Core

Backtracking typically explores assignments through depth-first recursive search.

Compare with this

Used byEuler Tour

Graph Traversal · Core

Euler-tour based tree traversals are commonly produced by depth-first traversal order.

Compare with this

Used byPlanar Embedding

Graph Traversal · Extended

Planar Embedding uses Depth-First Search as a subroutine, representation, or supporting idea while ordering edges around vertices so a planar graph can be drawn without crossings.

Compare with this