Graph BFS and DFS Interview Patterns
Graph traversal is one of the most tested interview topics. BFS (Breadth-First Search) and DFS (Depth-First Search) are the two fundamental algorithms — all other graph algorithms build on them. The key skill: recognize which traversal is appropriate and handle visited state correctly.
BFS Template
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
BFS explores level by level — all nodes at distance 1, then distance 2, etc. This guarantees shortest path in unweighted graphs. Time: O(V+E). Space: O(V) for the queue.
DFS Template (Iterative and Recursive)
# Recursive DFS
def dfs(graph, node, visited):
visited.add(node)
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Iterative DFS (avoids recursion limit)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited: continue
visited.add(node)
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
Pattern 1: Number of Islands (Grid BFS/DFS)
def num_islands(grid):
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r = rows or c = cols or grid[r][c] != '1': return
grid[r][c] = '0' # mark visited by sinking
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r+dr, c+dc)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
Pattern 2: Shortest Path in Grid (BFS)
def shortest_path(grid, start, end):
rows, cols = len(grid), len(grid[0])
queue = deque([(start[0], start[1], 0)]) # (row, col, distance)
visited = {(start[0], start[1])}
while queue:
r, c, dist = queue.popleft()
if (r, c) == (end[0], end[1]): return dist
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==0 and (nr,nc) not in visited:
visited.add((nr,nc))
queue.append((nr,nc,dist+1))
return -1 # no path
BFS guarantees shortest path for unit-weight edges. Add distance to queue state — do not track distances separately.
Pattern 3: Course Schedule (Cycle Detection with DFS)
def can_finish(numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]
for a, b in prerequisites: graph[b].append(a)
# 0=unvisited, 1=in progress, 2=done
state = [0] * numCourses
def dfs(node):
if state[node] == 1: return False # cycle
if state[node] == 2: return True # already processed
state[node] = 1
for neighbor in graph[node]:
if not dfs(neighbor): return False
state[node] = 2
return True
return all(dfs(i) for i in range(numCourses))
Three-color DFS: unvisited (0), in-progress/gray (1), done/black (2). A back edge to a gray node = cycle.
Pattern 4: Multi-Source BFS
# "01 Matrix": distance to nearest 0 for each cell
def update_matrix(mat):
rows, cols = len(mat), len(mat[0])
dist = [[float('inf')]*cols for _ in range(rows)]
queue = deque()
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
dist[r][c] = 0
queue.append((r, c)) # seed ALL zeros simultaneously
while queue:
r, c = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc dist[r][c]+1:
dist[nr][nc] = dist[r][c]+1
queue.append((nr,nc))
return dist
Add ALL source nodes to the queue before starting BFS. The wave expands simultaneously from all sources. Equivalent to adding a virtual source node connected to all real sources.
BFS vs DFS: When to Use Which
- BFS: shortest path in unweighted graph, level-order traversal, minimum steps
- DFS: cycle detection, topological sort, connected components, maze solving (any path)
- Both work: number of islands, number of connected components
🏢 Asked at: Atlassian Interview Guide