Pattern Guide
BFS & DFS — Graph Traversal
"BFS for shortest paths. DFS for everything else."
Master BFS (level-order, shortest path, multi-source) and DFS (components, cycles, flood fill, topological sort). These two primitives underpin almost every graph algorithm.
22 min readgraph problems →
Problems you can solve with this pattern
11 problems · click any to start solving
BFS on grid (4-directional)
const dr = [1, 0, -1, 0];
const dc = [0, 1, 0, -1];
const vis = Array.from({length: n}, () => new Array(m).fill(false));
const bfs = (startR, startC) => {
const q = new Queue([[startR, startC]]);
vis[startR][startC] = true;
while (!q.isEmpty()) {
const [r, c] = q.dequeue();
for (let i = 0; i < 4; i++) {
const nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && !vis[nr][nc]) {
vis[nr][nc] = true;
q.enqueue([nr, nc]);
}
}
}
};Every graph problem reduces to one of two primitives: BFS or DFS. BFS explores level by level (all nodes at distance 1, then distance 2...) making it perfect for shortest paths. DFS goes deep before wide, making it ideal for connectivity, cycles, and topological ordering. Once you internalize when to use each and their templates, you can solve almost any graph problem.
BFS vs DFS — When to Use Which
| Use BFS When... | Use DFS When... |
|---|---|
| Need shortest path (unweighted) | Need to find all connected components |
| Need level-by-level processing | Cycle detection |
| Multi-source simultaneous spread | Topological sort (Kahn's or DFS-based) |
| Word ladder / state-space minimum steps | Finding SCCs (Kosaraju's) |
| Flood fill with minimum expansion | Tree traversal (preorder/inorder/postorder) |
For shortest path: always BFS. With BFS, all nodes at distance x are visited before any node at distance x+1. The first time we reach the target, we're guaranteed it's the shortest path. DFS can find A path but not guaranteed shortest.
Core Templates
BFS on grid (4-directional)
const dr = [1, 0, -1, 0];
const dc = [0, 1, 0, -1];
const vis = Array.from({length: n}, () => new Array(m).fill(false));
const bfs = (startR, startC) => {
const q = new Queue([[startR, startC]]);
vis[startR][startC] = true;
while (!q.isEmpty()) {
const [r, c] = q.dequeue();
for (let i = 0; i < 4; i++) {
const nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && !vis[nr][nc]) {
vis[nr][nc] = true;
q.enqueue([nr, nc]);
}
}
}
};DFS on graph (adjacency list)
const vis = new Array(n).fill(false);
const dfs = (src) => {
vis[src] = true;
for (const neighbor of adj[src]) {
if (!vis[neighbor]) dfs(neighbor);
}
};
// Count connected components
let components = 0;
for (let i = 0; i < n; i++) {
if (!vis[i]) { dfs(i); components++; }
}Cycle detection in directed graph (vis + path arrays)
const vis = new Array(n).fill(false);
const path = new Array(n).fill(false); // currently in DFS stack
const hasCycle = (src) => {
vis[src] = true;
path[src] = true;
for (const node of adj[src]) {
if (!vis[node]) { if (hasCycle(node)) return true; }
else if (path[node]) return true; // back edge = cycle
}
path[src] = false; // leaving this path
return false;
};Undirected graph adjacency matrix trick: For adj[i][j] symmetric matrix, to avoid processing each edge twice, iterate only the top-right triangle:
Top-right is more common in practice.
for (let i = 0; i < n; i++) for (let j = i+1; j < n; j++)Top-right is more common in practice.
Kosaraju's SCC Algorithm
SCC exists only in directed graphs. A strongly connected component is a maximal set where every node is reachable from every other node. Kosaraju's algorithm:
1. Run DFS on original graph, record finish times (push to stack when done)
2. Reverse all edges
3. Process nodes by decreasing finish time (pop from stack). Each DFS on reversed graph = one SCC.
1. Run DFS on original graph, record finish times (push to stack when done)
2. Reverse all edges
3. Process nodes by decreasing finish time (pop from stack). Each DFS on reversed graph = one SCC.
Kosaraju's SCC
function kosaraju(adj) {
const n = adj.length;
const vis = new Array(n).fill(false);
const stack = [];
const adjRev = Array.from({length: n}, () => []);
// Step 1: DFS, record finish order
const dfs1 = (src) => {
vis[src] = true;
for (const node of adj[src]) if (!vis[node]) dfs1(node);
stack.push(src); // push when fully done
};
for (let i = 0; i < n; i++) if (!vis[i]) dfs1(i);
// Build reversed graph
vis.fill(false);
for (let i = 0; i < n; i++)
for (const node of adj[i]) adjRev[node].push(i);
// Step 2: DFS on reversed graph in finish-time order
const dfs2 = (src) => {
vis[src] = true;
for (const node of adjRev[src]) if (!vis[node]) dfs2(node);
};
let scc = 0;
while (stack.length) {
const src = stack.pop();
if (!vis[src]) { scc++; dfs2(src); }
}
return scc;
}Even More Problems
Graph algorithm selector:
- Unweighted shortest path → BFS
- Weighted shortest path (positive weights) → Dijkstra
- Minimax/maximin path → Dijkstra with max instead of sum
- Negative weights → Bellman-Ford
- All-pairs shortest path → Floyd-Warshall
- Minimum spanning tree → Kruskal (sort edges + UF) or Prim (Dijkstra-like)
- Cycle detection / topo sort → DFS with color states or Kahn's BFS
- Strongly connected components → Kosaraju (2 DFS) or Tarjan
- Eulerian path → Hierholzer's (DFS, post-order insert to front)
- Unweighted shortest path → BFS
- Weighted shortest path (positive weights) → Dijkstra
- Minimax/maximin path → Dijkstra with max instead of sum
- Negative weights → Bellman-Ford
- All-pairs shortest path → Floyd-Warshall
- Minimum spanning tree → Kruskal (sort edges + UF) or Prim (Dijkstra-like)
- Cycle detection / topo sort → DFS with color states or Kahn's BFS
- Strongly connected components → Kosaraju (2 DFS) or Tarjan
- Eulerian path → Hierholzer's (DFS, post-order insert to front)