Adjacency list is the standard graph representation. First step for BFS/DFS problems.
from collections import defaultdict
graph = defaultdict(list)
# or: {i: [] for i in range(n)}BFS explores level-by-level. Gives shortest path in unweighted graphs.
from collections import deque
q = deque([start])
visited = {start}
while q:
node = q.popleft()
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
q.append(nb)Iterative DFS avoids recursion limits. Same time complexity, explicit stack.
stack = [start]
visited = {start}
while stack:
node = stack.pop()
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
stack.append(nb)Recursive DFS is the most natural graph traversal. Watch for stack overflow on deep graphs.
def dfs(node):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs(nb)Undirected edges add both directions. Foundation for graph construction.
graph[u].append(v)
graph[v].append(u)Initialize queue with all sources. BFS radiates outward in parallel from all starting points.
q = deque()
for i in range(R):
for j in range(C):
if grid[i][j] == 2: q.append((i, j, 0))
while q:
i, j, t = q.popleft()
for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
ni, nj = i+di, j+dj
if 0<=ni<R and 0<=nj<C and grid[ni][nj]==1:
grid[ni][nj] = 2
q.append((ni, nj, t+1))Start DFS from border O's to mark safe cells. Everything else gets captured.
for i in range(R):
for j in range(C):
if (i in (0, R-1) or j in (0, C-1)) and board[i][j] == 'O':
dfs(i, j) # mark border O as safeBFS-based topo sort processes zero-indegree nodes first. Detects cycles if order is incomplete.
from collections import deque
q = deque(n for n in range(V) if indeg[n] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)BFS = shortest path. DFS = exhaustive search. For grids: shortest → BFS, reachability → DFS, regions → either.
BFS vs DFS — DECISION GUIDE
────────────────────────────
USE BFS when:
□ Shortest path in unweighted graph
□ Level-by-level processing needed
□ Closest node satisfying condition
□ Minimum steps / moves / transforms
Examples: word ladder, shortest grid path, rotten oranges
USE DFS when:
□ Exhaustive search / enumerate all paths
□ Cycle detection, connected components
□ Topological sort
□ Tree traversals (inherently DFS)
□ Backtracking problems
Examples: number of islands, path exists, clone graph
COMPLEXITY: both O(V + E)
SPACE:
BFS: O(width) — queue stores entire level
DFS: O(height/depth) — stack stores path
GRID PROBLEMS:
"Shortest path" → BFS (always)
"Can you reach?" → DFS (simpler) or BFS
"Count regions" → DFS or BFS (both fine)
"All paths" → DFS with backtrackingUnion-Find excels at dynamic connectivity queries. BFS/DFS excels at traversal and shortest paths. Different tools for different jobs.
UNION-FIND vs BFS/DFS FOR COMPONENTS
─────────────────────────────────────
BFS/DFS: UNION-FIND:
One-shot traversal Online / streaming edges
O(V + E) per query O(α(n)) ≈ O(1) per operation
Need adjacency list Works with edge list directly
Simpler code Better for dynamic connectivity
USE UNION-FIND when:
□ Edges arrive one at a time
□ "Are X and Y connected?" queries
□ Need to merge groups repeatedly
□ Kruskal's MST algorithm
□ Count components as edges added
Examples: redundant connection, accounts merge
USE BFS/DFS when:
□ Need to traverse/visit nodes in order
□ Need shortest path
□ Graph already built as adjacency list
□ Need to process each component's nodes
Examples: number of islands, clone graph
HYBRID: use Union-Find to detect components,
then BFS/DFS within each componentAdjacency list is the default for interviews. Use matrix for dense graphs or O(1) edge lookup. Edge list for MST.
GRAPH REPRESENTATIONS
─────────────────────
ADJACENCY LIST: graph[u] = [v1, v2, ...]
+ Space: O(V + E) — sparse-friendly
+ Iterate neighbors: O(degree)
+ Add edge: O(1)
- Check edge exists: O(degree)
Best for: most problems, sparse graphs
ADJACENCY MATRIX: graph[u][v] = weight
+ Check edge exists: O(1)
+ Dense graph efficient
- Space: O(V²) — wasteful if sparse
- Iterate neighbors: O(V)
Best for: dense graphs, Floyd-Warshall
EDGE LIST: [(u, v, weight), ...]
+ Simple, compact
+ Natural for Kruskal's (sort by weight)
- Check edge/neighbors: O(E)
Best for: Kruskal's MST, reading input
PYTHON PATTERNS:
Adj list: graph = defaultdict(list)
graph[u].append(v)
Matrix: graph = [[0]*n for _ in range(n)]
Weighted: graph[u].append((v, weight))Directed uses 3 colors (gray = on stack = cycle). Undirected just checks visited + skip parent. Don't mix them up.
CYCLE DETECTION — DIRECTED vs UNDIRECTED
────────────────────────────────────────
UNDIRECTED GRAPH:
DFS: if neighbor is visited AND not parent → cycle
Union-Find: if find(u) == find(v) before union → cycle
DIRECTED GRAPH:
DFS with 3 colors:
WHITE (0) = unvisited
GRAY (1) = in current DFS path (on stack)
BLACK (2) = fully processed
If we visit a GRAY node → back edge → CYCLE
Kahn's BFS (topological sort):
If not all nodes processed → cycle exists
KEY DIFFERENCE:
Undirected: any back edge = cycle (skip parent)
Directed: only GRAY (in-stack) back edge = cycle
BLACK (cross/forward edge) is OK!
TEMPLATE:
directed: color[u] = GRAY → visit → color[u] = BLACK
undirected: visited[u] = True, pass parent to avoid
false positive on the edge we came fromMin-heap BFS for weighted graphs. Skip stale entries (d > dist[u]). O((V+E) log V). Non-negative weights only.
import heapq
from collections import defaultdict
def dijkstra(graph, src, n):
dist = [float('inf')] * n
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue # stale entry
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return distBasic Union-Find without optimizations. find walks to root. union links roots. Returns False if already connected.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return False
self.parent[px] = py
return TruePath compression: point directly to root. Union by rank: attach smaller tree under larger. Near O(1) amortized.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return TrueThree colors: white (unvisited), gray (in current path), black (finished). Gray → gray = cycle in directed graph.
def hasCycle(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 0=white, 1=gray (in stack), 2=black (done)
color = [0] * n
def dfs(u):
color[u] = 1 # gray: entering
for v in graph[u]:
if color[v] == 1: return True # back edge → cycle
if color[v] == 0 and dfs(v): return True
color[u] = 2 # black: done
return False
return any(color[i] == 0 and dfs(i) for i in range(n))Track parent to avoid counting the edge we came from. If neighbor is visited and not parent → cycle.
def hasCycleUndirected(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
def dfs(u, parent):
visited[u] = True
for v in graph[u]:
if not visited[v]:
if dfs(v, u): return True
elif v != parent: # visited and not parent → cycle
return True
return False
return any(not visited[i] and dfs(i, -1) for i in range(n))2-color BFS: assign opposite colors to neighbors. If same color conflict → not bipartite. Check all components.
from collections import deque
def isBipartite(graph):
n = len(graph)
color = [-1] * n
for start in range(n):
if color[start] != -1: continue
q = deque([start])
color[start] = 0
while q:
u = q.popleft()
for v in graph[u]:
if color[v] == -1:
color[v] = 1 - color[u]
q.append(v)
elif color[v] == color[u]:
return False
return TrueFlood-fill DFS: mark visited by changing '1' to '0'. Each DFS call covers one island. Count DFS starts.
def numIslands(grid):
m, n = len(grid), len(grid[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
grid[i][j] = '0' # mark visited
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return countBFS guarantees shortest path in unweighted grid. Mark visited WHEN ADDING to queue (not when popping). O(m*n).
from collections import deque
def shortestPath(grid, start, end):
m, n = len(grid), len(grid[0])
q = deque([(start[0], start[1], 0)])
visited = {(start[0], start[1])}
while q:
r, c, dist = q.popleft()
if (r, c) == tuple(end):
return dist
for dr, dc in (0,1),(0,-1),(1,0),(-1,0):
nr, nc = r + dr, c + dc
if (0 <= nr < m and 0 <= nc < n
and grid[nr][nc] == 0
and (nr, nc) not in visited):
visited.add((nr, nc))
q.append((nr, nc, dist + 1))
return -1HashMap maps original → clone. DFS creates clone before recursing neighbors to handle cycles.
def cloneGraph(node):
if not node: return None
cloned = {}
def dfs(n):
if n in cloned: return cloned[n]
copy = Node(n.val)
cloned[n] = copy
for nb in n.neighbors:
copy.neighbors.append(dfs(nb))
return copy
return dfs(node)Reverse flow: DFS from ocean edges inward (uphill). Intersection of pacific-reachable and atlantic-reachable cells.
def pacificAtlantic(heights):
m, n = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r, c, visit, prev_h):
if (r, c) in visit or r < 0 or r >= m or c < 0 or c >= n:
return
if heights[r][c] < prev_h: return
visit.add((r, c))
for dr, dc in (0,1),(0,-1),(1,0),(-1,0):
dfs(r+dr, c+dc, visit, heights[r][c])
for c in range(n):
dfs(0, c, pac, 0) # top edge → pacific
dfs(m-1, c, atl, 0) # bottom edge → atlantic
for r in range(m):
dfs(r, 0, pac, 0) # left edge → pacific
dfs(r, n-1, atl, 0) # right edge → atlantic
return list(pac & atl)Sort edges by weight. Greedily add edge if it connects two components (Union-Find). Stop at n-1 edges.
def kruskal(n, edges):
# edges = [(weight, u, v), ...]
edges.sort()
uf = UnionFind(n)
mst_weight = 0
mst_edges = 0
for w, u, v in edges:
if uf.union(u, v):
mst_weight += w
mst_edges += 1
if mst_edges == n - 1:
break
return mst_weight if mst_edges == n - 1 else -1Dijkstra from source k. Answer is max distance (time for signal to reach farthest node). -1 if not all reachable.
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {k: 0}
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist.get(u, float('inf')): continue
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float('inf')):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return max(dist.values()) if len(dist) == n else -1Build ordering graph from adjacent word pairs. Topological sort gives valid alphabet. Detect cycles for invalid input.
def alienOrder(words):
graph = {c: set() for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1[:len(w2)] == w2:
return "" # invalid: prefix comes after
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topo sort
color = {} # 1=gray, 2=black
order = []
def dfs(c):
if c in color: return color[c] == 2
color[c] = 1
for nb in graph[c]:
if not dfs(nb): return False
color[c] = 2
order.append(c)
return True
return ''.join(reversed(order)) if all(dfs(c) for c in graph) else ''BFS with implicit graph: each word connects to words differing by one letter. Try all 26 replacements at each position.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
words = set(wordList)
if endWord not in words: return 0
q = deque([(beginWord, 1)])
visited = {beginWord}
while q:
word, steps = q.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nw = word[:i] + c + word[i+1:]
if nw == endWord: return steps + 1
if nw in words and nw not in visited:
visited.add(nw)
q.append((nw, steps + 1))
return 0Recursive DFS on a grid with bounds + color check. Same pattern for island counting, connected regions, etc.
def fill(grid, i, j, old, new):
if i < 0 or i >= len(grid): return
if j < 0 or j >= len(grid[0]): return
if grid[i][j] != old: return
grid[i][j] = new
for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:
fill(grid, i+di, j+dj, old, new)Loop over all nodes, DFS/BFS from unvisited ones, increment count each time. Works on adjacency list or matrix.
visited = set()
count = 0
for node in range(n):
if node not in visited:
count += 1
stack = [node]
while stack:
cur = stack.pop()
if cur in visited: continue
visited.add(cur)
stack.extend(graph[cur])Kahn's algorithm: start from zero in-degree nodes, peel layers. If len(order) < n, there's a cycle.
from collections import deque, defaultdict
in_deg = [0] * n
graph = defaultdict(list)
for a, b in edges:
graph[b].append(a)
in_deg[a] += 1
q = deque(i for i in range(n) if in_deg[i] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for nb in graph[node]:
in_deg[nb] -= 1
if in_deg[nb] == 0:
q.append(nb)