DFS (Depth-First Search)
Use when: exhaustive exploration, connected components, cycle detection, path existence, island counting.
Signal words: number of islands, connected components, all paths, can you reach, flood fill.
Core Idea
Go deep before going wide. Use recursion (or an explicit stack) to explore one branch fully before backtracking.
Template (recursive)
def dfs(node, visited):
if node in visited:
return
visited.add(node)
# process node
for neighbor in graph[node]:
dfs(neighbor, visited)Template (grid)
DIRS = [(0,1),(0,-1),(1,0),(-1,0)]
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != target or (r, c) in visited:
return
visited.add((r, c))
for dr, dc in DIRS:
dfs(r + dr, c + dc)DFS vs BFS
- DFS: path existence, cycle detection, all paths, connected components
- BFS: shortest path, minimum steps