Graph BFS / Shortest Path
Explore in rings of increasing distance. The first time BFS reaches a node it does so by a shortest path.
GraphsO(V + E)New12 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
shortest path unweighted
minimum steps
rotting oranges
word ladder
The template
Get this into muscle memory, then adapt the condition per problem.
const q = [start]; const dist = new Map([[start, 0]]);
while (q.length) {
const u = q.shift()!;
for (const v of adj(u)) if (!dist.has(v)) {
dist.set(v, dist.get(u)! + 1);
q.push(v);
}
} Watch Breadth First SearchIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Minimum number of steps on equal-cost edges means BFS, not DFS.
- 2Mark nodes visited when you enqueue them, not when you dequeue them.
- 3Multi-source BFS starts with every source already in the queue.
Drill it
Every problem in the bank that uses this pattern.
0 / 12 solved