Depth-First Search (DFS)
DSA · Graphs
Theory
DFS explores as far as possible along one branch before backtracking, using recursion or an explicit stack and a visited set. It visits every reachable vertex in O(V + E) time. DFS is the basis for detecting cycles, finding connected components, topological sorting and solving mazes.
Why we use it
It explores complete paths and naturally fits recursive problems on graphs and grids.
When to use it
Use DFS to check connectivity, count islands in a grid, detect cycles, topological sort, and explore all paths (backtracking).
How it works
- dfs(u): mark u visited
- For each neighbour v of u
- v not visited? Yes: dfs(v). No: Skip.
- Backtrack when all neighbours are done
Syntax
def dfs(v):
visited.add(v)
for nb in graph[v]:
if nb not in visited:
dfs(nb)
Time: O(V + E) Space: O(V)Example
grid = [
"11000",
"11000",
"00100",
"00011",
]
rows, cols = len(grid), len(grid[0])
seen = set()
def dfs(r, c):
if r < 0 or c < 0 or r >= rows or c >= cols:
return
if grid[r][c] != "1" or (r, c) in seen:
return
seen.add((r, c))
dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in seen:
islands += 1
dfs(r, c)
print("Number of islands:", islands)Key points
- Goes deep before backtracking
- Recursion or an explicit stack
- Finds components and cycles
- O(V + E) time