patternDSA/Depth-First Search

Core Pattern → Pattern 07

Depth-First Search

Explore as deep as possible before backtracking. One visited set prevents infinite loops. Works on any graph, grid, or tree.

Frequency:★★★★★

·~40 min·Intermediate·2 problems

Prev Breadth-First Search (BFS)

The Core Shock

Explore a graph without a visited set — infinite loop. With one — O(V+E)

No Visited Set

Infinite loop

Any cycle → revisit forever → stack overflow

O(∞)

With Visited Set

Every node once

V nodes + E edges — nothing visited twice

O(V+E)

The insight: a visited set transforms an infinite problem into a finite one. Each node enters the visited set exactly once. The DFS explores the call stack (recursive) or an explicit stack (iterative) — going as deep as possible before backtracking to try other branches.

Two DFS Implementations

Two implementations, same algorithm. Know both cold.

Recursive DFS

The call stack IS the DFS stack. Mark visited, process node, recurse into unvisited neighbors. Elegant and readable. Limited by Python's recursion depth (~1000 by default).

Use when: Use when: graph depth is bounded, code clarity matters, or backtracking state is needed (path problems).

All Paths Source→TargetTree DFSCycle DetectionConnected Components

Iterative DFS

Explicit stack replaces call stack. Identical traversal order, no recursion limit. Push neighbors in reverse order to match recursive left-to-right ordering.

Use when: Use when: graph can be very deep (100k+ nodes), recursion limit is a concern, or iterative style is preferred.

Number of Islands (deep grids)Large Graph TraversalIterative BacktrackingBFS/DFS comparison

The 3-Step DFS Framework

The same three steps work for every DFS problem — graph or grid.

Build the Graph (or Recognize the Grid)

From an edge list, build an adjacency list. For grids, the graph is implicit — neighbors are the 4 (or 8) adjacent cells. This step is often where interview bugs live.

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # undirected

Always clarify: directed or undirected? Weighted or unweighted? Can there be self-loops? Build adjacency list, not adjacency matrix (O(V²) space).

Initialize Visited + Call DFS

Create a visited set (or boolean array). For disconnected graphs, call DFS from every unvisited node in a for-loop — not just from node 0.

visited = set()
for node in range(n):
    if node not in visited:
        dfs(node, visited)

The outer for-loop handles disconnected graphs. Without it, you only traverse the component containing the start node.

Mark Visited Before Recursing

Add the current node to visited BEFORE calling DFS on neighbors. Marking after is a race condition in graphs — two paths can both try to visit the same node simultaneously.

def dfs(node):
    visited.add(node)   # mark BEFORE recursing
    for nb in graph[node]:
        if nb not in visited:
            dfs(nb)

Mark before recursing, not after. Mark before, not inside the neighbor check. This is the single most common DFS ordering bug.

Pattern Recognition

DFS vs BFS — the most important graph decision.

Use DFS When

"Find ALL paths from source to target"

Detect cycles in directed/undirected graph

Count or identify connected components

Flood fill — mark entire connected region

"Can you reach target from source?"

Topological sort (post-order DFS)

Solve puzzles / mazes with backtracking

Check if graph is bipartite

Use BFS Instead When

"Shortest path in unweighted graph"

"Minimum steps / hops to reach target"

Level-order traversal needed

Closest node satisfying a condition

Word ladder / transformation chains

Rotten Oranges — simultaneous spreading

Binary tree level-order traversal

"Minimum moves in a grid"

On this page