BFS & DFS Graphs — Master Recap & Cheatsheet

BFS & DFS on Graphs — Master Cheatsheet

The 7 Core Patterns

Pattern	Key Technique	Representative Problem
DFS Flood Fill	Mark in-place	Number of Islands
BFS Shortest Path	Layer BFS	Shortest Path Binary Matrix
Multi-Source BFS	All sources at t=0	Rotting Oranges, 01 Matrix
Boundary DFS	Mark safe from border	Surrounded Regions
BFS with State	visited = (pos, state)	Open the Lock
Weighted BFS	Dijkstra heap	Network Delay, Min Effort
0-1 BFS	Deque (0→front, 1→back)	Minimum Cost Grid Path

DFS Template

def dfs(r, c):
    if out_of_bounds or visited: return
    mark_visited(r, c)
    for dr, dc in DIRS:
        dfs(r+dr, c+dc)

BFS Template

from collections import deque
q = deque([(start_r, start_c, 0)])
visited = {(start_r, start_c)}
while q:
    r, c, dist = q.popleft()
    for dr, dc in DIRS:
        nr, nc = r+dr, c+dc
        if valid and not visited:
            visited.add((nr, nc))
            q.append((nr, nc, dist+1))

Dijkstra Template

import heapq
dist = {node: inf}; dist[start] = 0
heap = [(0, start)]
while heap:
    d, u = heapq.heappop(heap)
    if d > dist[u]: continue
    for v, w in adj[u]:
        if dist[u]+w < dist[v]:
            dist[v] = dist[u]+w
            heapq.heappush(heap, (dist[v], v))

Union-Find Template

parent = list(range(n))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]  # path compression
        x = parent[x]
    return x
def union(a, b):
    a, b = find(a), find(b)
    if a == b: return False
    parent[a] = b; return True

Complexity Summary

Algorithm	Time	Space
DFS/BFS Grid	O(R*C)	O(R*C)
BFS Shortest (unweighted)	O(V+E)	O(V)
Dijkstra	O(E log V)	O(V+E)
Bellman-Ford	O(V*E)	O(V)
Topological Sort	O(V+E)	O(V)
Union-Find	O(α(n)) per op	O(n)

Common Pitfalls

Forgetting to mark visited before push → infinite loops
Not handling disconnected graphs → loop all nodes
BFS for weighted graphs → must use Dijkstra
DFS for shortest path → wrong, use BFS
Multi-source: forget to init all sources → wrong distances
Word search: forgetting to unmark on backtrack → wrong answers
Boundary DFS: 3-step always → mark safe, flip bad, restore safe

Problem Index by Pattern

DFS Flood Fill: Islands (01,04,07,09,10,11,16,17), Flood Fill (02)

BFS Shortest Path: Rotting Oranges (06), 01 Matrix (07), Walls & Gates (08), Shortest Binary Matrix (13), Nearest Exit (25), Snakes & Ladders (26), Open Lock (27)

Multi-Source BFS: Rotting Oranges (06), 01 Matrix (07), As Far from Land (14)

Boundary DFS: Surrounded Regions (05), Enclaves (09), Closed Islands (17)

Graph BFS/DFS: Clone (21), Provinces (22), Keys & Rooms (23), Valid Path (24), Bipartite (40,41), Evaluate Division (43)

Weighted / Dijkstra: Min Effort (19), Network Delay (35), Cheapest Flights (36), Reachable Nodes (44)

Topological Sort: Course Schedule I & II (29,30)

Union-Find: Islands II (20), Valid Tree (31), Components (32), Redundant (33)