Depth-First Search (DFS)

Depth-First Search explores as far as possible along each branch before backtracking. It naturally reveals recursive structure, discovery/finish times, and supports topological sorting and strongly connected components detection.

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

Actions

Dive into Theory Try Simulation

Back: BFS Next: Dijkstra Algorithm