Graph Algorithms Interview Patterns: BFS, DFS, Dijkstra & More
Graph problems appear in roughly 25% of FAANG algorithm interviews. Mastering BFS, DFS, shortest path, and cycle detection gives you a systematic toolkit for grids, trees, network flow, and dependency problems.
Graph Representations
Choose your representation based on density and operations:
- Adjacency list — O(V+E) space, O(degree) neighbor lookup. Best for sparse graphs (most interview problems).
- Adjacency matrix — O(V²) space, O(1) edge existence. Best for dense graphs or when you need quick edge weight lookups.
- Edge list — O(E) space. Used in Kruskal’s MST algorithm.
from collections import defaultdict, deque
# Build adjacency list
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # undirected
BFS — Breadth-First Search
Use BFS for: shortest path in unweighted graphs, level-order traversal, minimum steps problems.
def bfs(graph, start):
visited = {start}
queue = deque([start])
dist = {start: 0}
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
dist[neighbor] = dist[node] + 1
queue.append(neighbor)
return dist
Grid BFS template (most common in interviews):
def bfs_grid(grid, start_r, start_c):
rows, cols = len(grid), len(grid[0])
visited = {(start_r, start_c)}
queue = deque([(start_r, start_c, 0)]) # (row, col, dist)
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
while queue:
r, c, d = queue.popleft()
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and (nr,nc) not in visited and grid[nr][nc] != '#':
visited.add((nr, nc))
queue.append((nr, nc, d+1))
DFS — Depth-First Search
Use DFS for: cycle detection, topological sort, connected components, path existence, backtracking.
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
# Iterative DFS (avoids recursion limit)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
stack.extend(graph[node])
Cycle Detection
Undirected graph — track parent in DFS:
def has_cycle_undirected(graph, n):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True
return False
for node in range(n):
if node not in visited:
if dfs(node, -1):
return True
return False
Directed graph — use 3-color DFS (white/gray/black or 0/1/2):
def has_cycle_directed(graph, n):
color = [0] * n # 0=unvisited, 1=in-stack, 2=done
def dfs(node):
color[node] = 1
for neighbor in graph[node]:
if color[neighbor] == 1:
return True # back edge = cycle
if color[neighbor] == 0 and dfs(neighbor):
return True
color[node] = 2
return False
return any(color[i] == 0 and dfs(i) for i in range(n))
Dijkstra’s Algorithm — Shortest Path (Weighted)
Time: O((V+E) log V) with min-heap. Use for non-negative edge weights.
import heapq
def dijkstra(graph, src, n):
dist = [float('inf')] * n
dist[src] = 0
heap = [(0, src)] # (distance, node)
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 dist
When to use Bellman-Ford instead: negative edge weights (detect negative cycles). Time: O(V·E).
Union-Find for Connected Components
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])
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 True
Classic Graph Interview Problems
| Problem | Algorithm | Key Insight |
|---|---|---|
| Number of Islands | BFS/DFS | Mark visited cells, count components |
| Word Ladder | BFS | Shortest path, each word = node |
| Course Schedule | DFS cycle detection | Directed graph, detect back edge |
| Network Delay Time | Dijkstra | Single-source shortest path |
| Minimum Spanning Tree | Kruskal / Prim | Union-Find or min-heap |
| Alien Dictionary | Topological sort | Build ordering constraints from char pairs |
| Bipartite Check | BFS 2-coloring | Alternate colors; conflict = not bipartite |
Interview Checklist
- Clarify: directed vs undirected, weighted vs unweighted, connected vs disconnected
- Ask: can there be cycles? self-loops? multiple edges?
- For grid problems: confirm movement directions (4-directional vs 8-directional)
- Always track visited to avoid infinite loops
- State whether you’d use BFS (shortest) or DFS (existence/backtracking) and why
- Know time complexity: BFS/DFS = O(V+E), Dijkstra = O((V+E) log V)
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use BFS vs DFS for graph problems?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Use BFS when you need the shortest path in an unweighted graph (it explores level by level, guaranteeing the first path found is shortest). Use DFS for cycle detection, topological sort, connected components, path existence, and backtracking problems. DFS uses less memory on wide graphs; BFS uses less memory on deep graphs.” }
},
{
“@type”: “Question”,
“name”: “How do you detect a cycle in a directed graph?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Use 3-color DFS: mark each node as unvisited (0), in-stack/gray (1), or fully processed (2). During DFS, if you reach a gray node (currently in the recursion stack), you have found a back edge, which means there is a cycle. This runs in O(V+E) time. For undirected graphs, track the parent and flag a cycle when you reach a visited non-parent neighbor.” }
},
{
“@type”: “Question”,
“name”: “What is the time complexity of Dijkstra's algorithm and when does it fail?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Dijkstra's runs in O((V+E) log V) using a min-heap. It fails (produces incorrect results) when graphs have negative edge weights, because it assumes once a node is finalized its distance is optimal. For negative weights, use Bellman-Ford O(V*E), which also detects negative cycles. For DAGs, topological-sort-based relaxation is even faster at O(V+E).” }
}
]
}