A
Nodes, edges, and the art of choosing the right traversal — BFS for shortest paths, DFS for connectivity and fill, topological sort for ordering, union-find for grouping, and Dijkstra when edges have weight. Grids are just implicit graphs; the algorithms are the same.
Almost every graph problem is the same walk from a starting node, and the only knob you turn is the container that holds “where to go next.” A queue(FIFO) explores in expanding rings — that's BFS, and the ring number is the shortest distance. A stackor recursion (LIFO) plunges down one path to the bottom before backtracking — that's DFS. Same graph, same start; swap the container and the behavior flips.
Picture standing on a node with a to-do list of places to explore. Every algorithm in this whole category is: pop a node, mark it, add its unvisited neighbors to the list, repeat. The only thing that changes the personality of the search is which end of the list you pull from.
BFS treats the source as the center of a pond and explores in ripples. Level 0 is the source, level 1 is everything one edge away, level 2 is everything two edges away:
BFS from S — the frontier grows outward in equal-distance shells
level 2
┌───────────┐
│ level 1 │
│ ┌─────┐ │
│ │ S │ │ ◄ level 0 — the source
│ │ (0) │ │
│ └─────┘ │
│ B C │ ◄ level 1 — every direct neighbor (dist 1)
└───────────┘
D E F G ◄ level 2 — neighbors-of-neighbors (dist 2)
queue over time: [S] → [B,C] → [C,D,E] → [D,E,F,G] → ...
└ pop S, push its neighbors, then drain THIS ring
completely before any node of the next ring.
The first time you reach a node, you reached it by the FEWEST edges.
So in an unweighted graph, level number = shortest distance from S.DFS, given the same graph and the same start, behaves completely differently: it commits to a single tendril, follows it to the bottom, then backtracks to take the road not yet travelled:
DFS from S — follow one path to its end, then back up and branch
S
│ go deep ↓
▼
A ──► B ──► D ◄ dive: S→A→B→D until D is a dead end
│
│ D done — backtrack ▲ to B, B done — back ▲ to A
▼
A ──► C ◄ now explore A's OTHER neighbor, C
│
▼
E ◄ dive again: C→E
visit order: S, A, B, D, (backtrack), C, E
└ one tendril at a time, all the way down, then unwind.
The call stack IS the path: each active frame is one step from S to "here".Half of all graph problems don't look like graphs — they're grids (number of islands, rotting oranges, walls & gates). The unlock: a grid is a graph you never have to build. Each cell is a node, and its four orthogonal neighbors (up / down / left / right) are its edges:
A grid is a graph you never have to build.
c-1 c c+1 the cell (r,c) and its
┌─────┬─────┬─────┐ 4 implicit edges:
r-1│ │ up │ │
├─────┼─────┼─────┤ (r-1,c)
r │left │(r,c)│right│ ▲
├─────┼─────┼─────┤ (r,c-1) ◄─ (r,c) ─► (r,c+1)
r+1│ │down │ │ ▼
└─────┴─────┴─────┘ (r+1,c)
neighbors = for [dr,dc] of [[1,0],[-1,0],[0,1],[0,-1]]:
(r+dr, c+dc) — if in bounds and not blocked
No adjacency list, no Map — the four deltas ARE the edges.You compute neighbors on the fly with the four deltas [[1,0],[-1,0],[0,1],[0,-1]], guarded by a bounds check. Once you see this, every grid problem becomes a plain BFS or DFS — same templates, just a [r,c] tuple instead of a node id.
DFS is the recursion you can write half-asleep: stop if seen, mark, recurse into each neighbor. The call stack is the path back to the source.
dfs(node): # "dive": go as deep as possible first
if node already visited: # 1. STOP at things you've seen
return # (prevents infinite loops on cycles)
mark node visited # 2. claim it the moment you arrive
for each neighbor of node: # 3. plunge into the FIRST neighbor fully,
dfs(neighbor) # only then move to the next one
# the call stack remembers where to back up to.
# recursion = an implicit LIFO stack.BFS replaces that implicit stack with an explicit FIFO queue. The one line that earns its keep is marking visited on enqueue, plus the level loop that lets you read off distance:
bfs(start): # "rings": explore in distance order
visited = { start } # mark ON ENQUEUE, never on dequeue
queue = [ start ] # FIFO — first in, first out
dist = 0
while queue not empty:
for each node in THIS level: # snapshot the level's size,
pop node from front # then drain exactly this ring
for each neighbor of node:
if neighbor not visited:
mark neighbor visited # ◄ BEFORE pushing, not after popping!
push neighbor to queue
dist = dist + 1 # one whole ring done → distance grows by 1queue.length at the top of each while iteration and process exactly that many nodes. Everything you process in that pass is the same distance from the source; bump the distance counter once per pass.Faced with an unfamiliar problem, don't guess the algorithm. Climb these rungs and the right tool falls out:
[r,c] cell.Say this out loud before you write BFS: “A node enters the queue at most once, and I mark it visited the instant it enters.” That single invariant is the difference between a correct BFS and the most common graph bug there is.
The classic failure: you only check visited when you dequeue a node. But between an enqueue and its dequeue, the queue can fill with duplicate copiesof the same node — two different neighbors both push it before either is processed. You then process it twice, double-count it, and in multi-source BFS you record the wrong distance (a farther source overwrites a nearer one).
visited in the same breath as queue.push(...), never at queue.shift(). Said differently: a node is “spoken for” the moment it's scheduled, not when it's served.adj[u].push(v) and adj[v].push(u). Forget one and half your graph silently vanishes.const stack = [[r,c]] and a whileloop — same LIFO order, no call-stack limit.A graph is a set of nodes (vertices) connected by edges. Edges can be directed or undirected, weighted or unweighted, and there can be cycles (unlike trees). The canonical representation is an adjacency list: Map<node, neighbor[]>.
A 2-D grid is an implicit graph: each cell is a node and its up/down/left/right neighbors are its edges. You never build the adjacency list explicitly — you compute neighbors on the fly with the four-direction deltas [[1,0],[-1,0],[0,1],[0,-1]].
Mandatory: a visited set. Without it, every traversal loops forever on cycles (or re-processes grid cells). Mark a node visited at enqueue/push time, not at process time, or BFS will enqueue the same node many times before it ever dequeues it.
The single most important skill in graph problems is choosing before you code:
O(V+E).V, a cycle exists.O(1) per operation with path compression + union by rank.O((V+E) log V).O(K·E).For grids of size R×C, substitute V = R·C and E = O(R·C) — at most 4 edges per cell.
visited only when you pop a node, multiple copies of the same node can sit in the queue simultaneously. Mark the node as visited the moment you push it. This is especially painful in multi-source BFS where two sources can both enqueue the same cell before either processes it — giving the wrong distance.DFS does not have this problem in the same way (recursive call stack prevents re-entry), but an iterative DFS stack can if you are not careful.
A. Seed the queue with the start node. BFS rings, DFS dives — the only difference is which end we pull from.Reach for a graph algorithm when the problem is about relationships between entities — reachability, ordering, grouping, or cost of traversal — and the relationships form a network rather than a simple linear or nested structure.
| "shortest path" / "minimum steps" in an unweighted grid or graph | BFS — levels naturally equal distance |
| "spread / rot / flood from multiple sources simultaneously" | multi-source BFS — seed all sources at level 0 |
| "prerequisites / can finish / valid ordering / alien dictionary" | topological sort + cycle detection (Kahn's BFS or DFS) |
| "connected components / are X and Y connected / redundant edge" | union-find (or DFS component count) |
| "weighted shortest path" with non-negative weights | Dijkstra with a min-heap |
| "cheapest / shortest with at most K stops / steps" | Bellman-Ford DP — relax edges at most K+1 times |
| "minimum cost to connect all points / nodes" | MST — Prim's (min-heap) or Kruskal (sort + union-find) |
n−1 edges).When → Shortest path or level-order traversal in an unweighted graph or grid. Always mark visited at enqueue time. The grid variant computes neighbors on-the-fly with direction deltas and a bounds check.
function bfs(graph: Map<number, number[]>, start: number): Set<number> {
const visited = new Set<number>([start]); // mark at enqueue, not dequeue
const queue: number[] = [start];
while (queue.length) {
const node = queue.shift()!; // dequeue front
for (const neighbor of graph.get(node) ?? []) {
if (visited.has(neighbor)) continue; // already seen
visited.add(neighbor); // mark BEFORE pushing
queue.push(neighbor);
}
}
return visited;
}
// Grid variant — 4-directional BFS
function bfsGrid(grid: string[][], sr: number, sc: number): void {
const rows = grid.length, cols = grid[0].length;
const visited = new Set<string>();
const queue: [number, number][] = [[sr, sc]];
visited.add(`${sr},${sc}`);
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
while (queue.length) {
const [r, c] = queue.shift()!;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // bounds
const key = `${nr},${nc}`;
if (visited.has(key) || grid[nr][nc] === '0') continue;
visited.add(key);
queue.push([nr, nc]);
}
}
}shift() or a deque library in production). For distance tracking, push [node, dist] or process level by level with a size snapshot.When → Connectivity, flood fill, component counting, or reachability in a grid or graph. Mutate the grid (or use a visited set) to mark cells. Prefer iterative DFS for grids larger than ~300×300 to avoid call-stack overflow.
// Recursive DFS flood fill — mutates grid in place (marks visited with 'X')
function dfs(grid: string[][], r: number, c: number): void {
const rows = grid.length, cols = grid[0].length;
if (r < 0 || r >= rows || c < 0 || c >= cols) return; // out of bounds
if (grid[r][c] !== '1') return; // not a target cell
grid[r][c] = 'X'; // mark visited by mutating (alternative: use a Set)
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}
// Count connected components (e.g. Number of Islands)
function countComponents(grid: string[][]): number {
let count = 0;
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] === '1') {
dfs(grid, r, c); // sinks the whole island
count++;
}
}
}
return count;
}const stack = [[r, c]] and loop.When → Ordering nodes in a DAG (course schedule, build order, alien alphabet). Also detects cycles for free: if the output order is shorter than numNodes, a cycle exists.
// Kahn's algorithm — BFS-based topological sort with cycle detection
function topoSort(numNodes: number, edges: [number, number][]): number[] {
const indegree = new Array(numNodes).fill(0);
const adj = new Map<number, number[]>();
for (let i = 0; i < numNodes; i++) adj.set(i, []);
for (const [u, v] of edges) {
adj.get(u)!.push(v);
indegree[v]++;
}
// Seed queue with all zero-indegree nodes
const queue: number[] = [];
for (let i = 0; i < numNodes; i++) {
if (indegree[i] === 0) queue.push(i);
}
const order: number[] = [];
while (queue.length) {
const node = queue.shift()!;
order.push(node);
for (const nb of adj.get(node)!) {
if (--indegree[nb] === 0) queue.push(nb); // prerequisite satisfied
}
}
// If order.length < numNodes → cycle detected (not a valid DAG)
return order.length === numNodes ? order : [];
}order.length < numNodes, some nodes never reached indegree 0, meaning they are part of a cycle — return [] or false.When → Grouping nodes into components, checking connectivity, or detecting the edge that closes a cycle. Near-O(1) per operation; much simpler than DFS when you only need component membership, not traversal order.
class UnionFind {
private parent: number[];
private rank: number[];
public components: number;
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i); // each node owns itself
this.rank = new Array(n).fill(0);
this.components = n;
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
union(x: number, y: number): boolean {
const px = this.find(x), py = this.find(y);
if (px === py) return false; // already in the same set → cycle!
// Union by rank keeps the tree flat
if (this.rank[px] < this.rank[py]) this.parent[px] = py;
else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
else { this.parent[py] = px; this.rank[px]++; }
this.components--;
return true;
}
}union(u, v). If it returns false, the edge connects two already-connected nodes — that is your redundant (cycle-closing) edge.Any graph with a cycle will loop forever without a visited set. Even acyclic graphs waste exponential time revisiting nodes if you skip it. Always allocate visited before the traversal and add nodes before exploring their neighbors.
If you only mark a node visited when you pop it from the queue, the same node can be pushed multiple times before it is ever popped — each copy then processes all its neighbors again. In a dense graph this silently gives wrong shortest-path distances and blows up runtime. Mark immediately on push.
When building an adjacency list for an undirected graph, add both directions: adj[u].push(v); adj[v].push(u);. For a directed graph, add only one. Getting this wrong in Course Schedule (directed) or Graph Valid Tree (undirected) produces silent incorrect answers.
Always check r < 0 || r >= rows || c < 0 || c >= cols before accessing grid[r][c]. On large grids (200×200+), recursive DFS can overflow the JavaScript call stack — convert to an explicit stack with an array and a while loop.