Model first
Before BFS, write: node = ? and edge = ?. Islands: node is cell, edge is 4-neighbor land. Course schedule: node is course, edge is prerequisite. Wrong model → beautiful code on the wrong graph.
Analogy: pond ripples + course prerequisites
BFS is dropping a pebble in a pond: the first ring is distance 1, then 2 — shortest hops in an unweighted graph. Topological sort is a degree plan: take courses with zero unmet prerequisites first; a cycle means you’re stuck forever.
BFS trace
from collections import deque, defaultdict
def bfs(start, g):
q = deque([start])
dist = {start: 0}
while q:
u = q.popleft()
for v in g[u]:
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return dist
# start=A edges A-B,A-C,B-D
# visit A(0), then B(1),C(1), then D(2)Map<String, Integer> bfs(String start, Map<String, List<String>> g) {
ArrayDeque<String> q = new ArrayDeque<>();
q.add(start);
Map<String, Integer> dist = new HashMap<>();
dist.put(start, 0);
while (!q.isEmpty()) {
String u = q.poll();
for (String v : g.getOrDefault(u, List.of())) {
if (!dist.containsKey(v)) {
dist.put(v, dist.get(u) + 1);
q.add(v);
}
}
}
return dist;
}
// start=A edges A-B,A-C,B-D
// visit A(0), then B(1),C(1), then D(2)Topo sort (Kahn) explained
Indegree = number of unmet prerequisites. Queue all zero-indegree nodes. Pop one, ‘take the course’, decrement neighbors; when a neighbor hits 0, enqueue. If you can’t take all n nodes, there’s a cycle.
def topo(n, edges):
g = defaultdict(list)
indeg = [0] * n
for u, v in edges:
g[u].append(v); indeg[v] += 1
q = deque([i for i in range(n) if indeg[i] == 0])
order = []
while q:
u = q.popleft(); order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else [] # [] => cycleList<Integer> topo(int n, int[][] edges) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) {
g.get(e[0]).add(e[1]);
indeg[e[1]]++;
}
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int u = q.poll();
order.add(u);
for (int v : g.get(u)) {
if (--indeg[v] == 0) q.add(v);
}
}
return order.size() == n ? order : List.of(); // empty => cycle
}Shortest paths cheat sheet
- Unweighted → BFS
- Weights only 0 or 1 → 0-1 BFS with deque
- Positive weights → Dijkstra with heap
- Negative weights → Bellman-Ford (rare in interviews)
What a good explanation sounds like
You: ‘Node is a course, directed edge prereq→course. I’ll Kahn-sort: queue zero-indegree courses, peel layers. If I can’t schedule n courses, there’s a cycle — return false.’
When to reach for this pattern
First move in every graph interview: model the graph — nodes, edges, directed?, weighted?. Wrong model wastes the whole session.
Core template + worked trace
Grid BFS — shortest path in unweighted grid:
from collections import deque
def shortest_path(grid):
# 0 empty, 1 blocked; start (0,0) to (n-1,m-1)
n, m = len(grid), len(grid[0])
if grid[0][0] or grid[n-1][m-1]:
return -1
q = deque([(0, 0, 1)]) # r, c, dist
seen = {(0, 0)}
while q:
r, c, d = q.popleft()
if (r, c) == (n - 1, m - 1):
return d
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 0 and (nr, nc) not in seen:
seen.add((nr, nc))
q.append((nr, nc, d + 1))
return -1
# 2x2 open grid: (0,0) dist1 → neighbors dist2 → (1,1) dist3int shortestPath(int[][] grid) {
// 0 empty, 1 blocked; start (0,0) to (n-1,m-1)
int n = grid.length, m = grid[0].length;
if (grid[0][0] != 0 || grid[n - 1][m - 1] != 0) return -1;
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[]{0, 0, 1}); // r, c, dist
boolean[][] seen = new boolean[n][m];
seen[0][0] = true;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1], d = cur[2];
if (r == n - 1 && c == m - 1) return d;
for (int[] dir : dirs) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 0 && !seen[nr][nc]) {
seen[nr][nc] = true;
q.add(new int[]{nr, nc, d + 1});
}
}
}
return -1;
}
// 2x2 open grid: (0,0) dist1 → neighbors dist2 → (1,1) dist3Kahn’s topological sort:
from collections import deque, defaultdict
def topo_order(n, edges):
indeg = [0] * n
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
q = deque([i for i in range(n) if indeg[i] == 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)
return order if len(order) == n else None # None ⇒ cycle
# n=4, edges=[(0,1),(0,2),(1,3),(2,3)] → e.g. [0,1,2,3]List<Integer> topoOrder(int n, int[][] edges) {
int[] indeg = new int[n];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
indeg[e[1]]++;
}
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int u = q.poll();
order.add(u);
for (int v : adj.get(u)) {
if (--indeg[v] == 0) q.add(v);
}
}
return order.size() == n ? order : null; // null ⇒ cycle
}
// n=4, edges=[(0,1),(0,2),(1,3),(2,3)] → e.g. [0,1,2,3]Edge cases & common bugs
Complexity — say it aloud
Interview talk track
You: ‘Unweighted shortest path → BFS by layers. I’ll mark visited on enqueue. For course order I’ll build indegrees and repeatedly take zero-indegree nodes; if I can’t place all n nodes, there’s a cycle.’
Practice set
- Number of Islands
- 01 Matrix / Shortest Path in Binary Matrix
- Word Ladder
- Course Schedule / Course Schedule II
- Alien Dictionary (topo)
- Clone Graph
- Network Delay Time (Dijkstra stretch)
- Pacific Atlantic Water Flow
Harder follow-up
Harder variant: Word Ladder — each word is a node; edges differ by one letter. BFS for shortest transformation. Optimize neighbors with a wildcard pattern map (h*t → hot, hit) instead of scanning the whole dictionary each step.
Pattern bank: more questions + efficient solutions
Five graph interview classics. Always name the node and edge before coding BFS/DFS/Dijkstra.
Q: Given an m × n binary grid, count the number of islands (4-connected groups of 1s).
# Number of Islands — O(mn) time
def num_islands(grid) -> int:
if not grid:
return 0
m, n, count = len(grid), len(grid[0]), 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"
dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1)
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
count += 1
dfs(i, j)
return count// Number of Islands — O(mn) time
int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length, count = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == '1') { count++; dfs(grid, i, j); }
return count;
}
void dfs(char[][] g, int i, int j) {
if (i < 0 || i >= g.length || j < 0 || j >= g[0].length || g[i][j] != '1') return;
g[i][j] = '0';
dfs(g, i + 1, j); dfs(g, i - 1, j); dfs(g, i, j + 1); dfs(g, i, j - 1);
}Q: There are numCourses labeled 0…n-1 and prerequisite pairs [a, b] meaning b → a. Return whether you can finish all courses (no cycle).
# Course Schedule (Kahn) — O(V+E)
from collections import deque, defaultdict
def can_finish(numCourses: int, prerequisites) -> bool:
g = defaultdict(list)
indeg = [0] * numCourses
for a, b in prerequisites:
g[b].append(a)
indeg[a] += 1
q = deque(i for i in range(numCourses) if indeg[i] == 0)
seen = 0
while q:
u = q.popleft()
seen += 1
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return seen == numCourses// Course Schedule (Kahn) — O(V+E)
boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> g = new ArrayList<>();
int[] indeg = new int[numCourses];
for (int i = 0; i < numCourses; i++) g.add(new ArrayList<>());
for (int[] e : prerequisites) { g.get(e[1]).add(e[0]); indeg[e[0]]++; }
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.add(i);
int seen = 0;
while (!q.isEmpty()) {
int u = q.poll();
seen++;
for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
}
return seen == numCourses;
}Q: Clone an undirected connected graph: each node has a value and a list of neighbors. Return a deep copy of the graph.
# Clone Graph — O(V+E)
from collections import deque
def clone_graph(node):
if not node:
return None
mp = {node: Node(node.val)}
q = deque([node])
while q:
cur = q.popleft()
for nei in cur.neighbors:
if nei not in mp:
mp[nei] = Node(nei.val)
q.append(nei)
mp[cur].neighbors.append(mp[nei])
return mp[node]// Clone Graph — O(V+E)
Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> mp = new HashMap<>();
mp.put(node, new Node(node.val));
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(node);
while (!q.isEmpty()) {
Node cur = q.poll();
for (Node nei : cur.neighbors) {
if (!mp.containsKey(nei)) {
mp.put(nei, new Node(nei.val));
q.add(nei);
}
mp.get(cur).neighbors.add(mp.get(nei));
}
}
return mp.get(node);
}Q: Word Ladder: given beginWord, endWord, and a word list, return the length of the shortest transformation sequence (change one letter at a time; each intermediate in the word list). Return 0 if impossible.
# Word Ladder — BFS shortest path
from collections import deque
def ladder_length(beginWord: str, endWord: str, wordList) -> int:
words = set(wordList)
if endWord not in words:
return 0
q = deque([(beginWord, 1)])
words.discard(beginWord)
while q:
w, d = q.popleft()
if w == endWord:
return d
chars = list(w)
for i in range(len(chars)):
orig = chars[i]
for c in "abcdefghijklmnopqrstuvwxyz":
chars[i] = c
nxt = "".join(chars)
if nxt in words:
words.remove(nxt)
q.append((nxt, d + 1))
chars[i] = orig
return 0// Word Ladder — BFS
int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return 0;
ArrayDeque<String> q = new ArrayDeque<>();
q.add(beginWord);
words.remove(beginWord);
int dist = 1;
while (!q.isEmpty()) {
int sz = q.size();
for (int s = 0; s < sz; s++) {
String w = q.poll();
if (w.equals(endWord)) return dist;
char[] ch = w.toCharArray();
for (int i = 0; i < ch.length; i++) {
char orig = ch[i];
for (char c = 'a'; c <= 'z'; c++) {
ch[i] = c;
String nxt = new String(ch);
if (words.remove(nxt)) q.add(nxt);
}
ch[i] = orig;
}
}
dist++;
}
return 0;
}Q: Network Delay Time: n nodes labeled 1…n, directed weighted edges times[i] = [u, v, w]. Signal starts at k. Return the time for all nodes to receive the signal, or −1 if impossible.
# Network Delay Time — Dijkstra O(E log V)
import heapq
from collections import defaultdict
def network_delay_time(times, n: int, k: int) -> int:
g = defaultdict(list)
for u, v, w in times:
g[u].append((v, w))
dist = {k: 0}
pq = [(0, k)]
while pq:
d, u = heapq.heappop(pq)
if d > dist.get(u, float("inf")):
continue
for v, w in g[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(pq, (nd, v))
return max(dist.values()) if len(dist) == n else -1// Network Delay Time — Dijkstra O(E log V)
int networkDelayTime(int[][] times, int n, int k) {
List<List<int[]>> g = new ArrayList<>();
for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
for (int[] e : times) g.get(e[0]).add(new int[]{e[1], e[2]});
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[k] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, k});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], u = cur[1];
if (d > dist[u]) continue;
for (int[] e : g.get(u)) {
int v = e[0], w = e[1], nd = d + w;
if (nd < dist[v]) {
dist[v] = nd;
pq.offer(new int[]{nd, v});
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == Integer.MAX_VALUE) return -1;
ans = Math.max(ans, dist[i]);
}
return ans;
}