Depth-First Search (DFS)

Explore graphs depth-first using recursion or a stack.

Traversal Style

Deep-Branch

Go deep then backtrack

Data Structure

Stack/Recursion

Call stack or explicit stack

Cycle Detection

Yes

Detects back edges

When to Use DFS

Exploring connectivity and components
Topological sorting (DAGs)
Detecting cycles in directed/undirected graphs
Finding articulation points & bridges
Generating mazes / pathfinding variants

Core Idea

Recursively visit an undiscovered vertex, then explore each undiscovered neighbor. Backtracking unwinds recursion revealing finishing order. Edge classification (tree, back, forward, cross) emerges from discovery/finish timestamps.

Algorithm Metrics

Time

O(V + E)

Space

O(V)

Traversal

Depthwise

Edge Types

Yes

Back: BFS Next: Dijkstra