Skip to content

Graph Traversals#

Graph problems dominate FAANG rounds. This page explains when to use BFS vs DFS; full problem sets live in 17. Graph.

Representations#

Style Best for Space
Adjacency list Sparse graphs, most interviews O(V + E)
Adjacency matrix Dense graphs, O(1) edge lookup O(V²)
Grid as graph Matrix problems — 4/8 directions O(1) extra if in-place visited 
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # undirected

See Graph data structure for representations and diagrams.

Use when: shortest path in unweighted graph, level-order, multi-source spread, "minimum steps."

from collections import deque

def bfs(start, graph):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)
                queue.append(nei)
Signal Example
Shortest path, unweighted Word Ladder, Rotting Oranges
Level / layer processing Binary tree level order
Multi-source Walls and Gates, 01 Matrix

Time: O(V + E) · Space: O(V)

Use when: explore all paths, connected components, cycle detection, topological sort, backtracking on graphs.

def dfs(node, graph, visited):
    visited.add(node)
    for nei in graph[node]:
        if nei not in visited:
            dfs(nei, graph, visited)
Signal Example
Count islands / flood fill Number of Islands
Cycle in directed graph Course Schedule
Path existence Keys and Rooms
Tree-like recursion Max depth, path sum

Time: O(V + E) · Space: O(V) recursion stack (or explicit stack)

Decision tree#

flowchart TD
    A[Graph problem] --> B{Shortest path unweighted?}
    B -->|Yes| C[BFS]
    B -->|No| D{Need all paths / cycles / topo?}
    D -->|Yes| E[DFS]
    D -->|No| F{Weighted non-negative edges?}
    F -->|Yes| G[Dijkstra]
    F -->|No| H{Only connectivity?}
    H -->|Yes| I[Union-Find]
    H -->|No| J[Re-read constraints]

BFS vs DFS summary#

BFS DFS
Data structure Queue (deque) Stack / recursion
First found path Shortest (unweighted) Not necessarily shortest
Memory Often wider (frontier) Often deeper (stack)
Typical patterns Shortest path, levels Components, cycles, backtrack

Practice#

Start with 17. Graph — BFS and DFS sections, then Blind 75 — Graph.