Lesson 23
Graphs & Breadth-First Search
Model anything connected — then explore it ring by ring.
01Why it matters & the intuition
Maps, social networks, dependency graphs, the web and state machines are graphs. BFS finds shortest paths in unweighted graphs and underpins everything from GPS to friend suggestions.
Think of it like…
Drop a stone in a pond: ripples reach everything 1 metre away, then 2 metres, then 3. BFS explores a graph the same way — every node at distance 1 before any node at distance 2 — so the first time it reaches a node is along a shortest path.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- discovered / in container
- processing now
- finished
03Key ideas
Vertices and edges
A graph is nodes (vertices) plus connections (edges). Edges can be directed or undirected, weighted or unweighted.
Adjacency list
Map<node, neighbour[]> — O(V + E) space, ideal for sparse real-world graphs. An adjacency matrix uses O(V²) but answers 'is there an edge?' in O(1).
BFS with a queue
Enqueue the start, mark it visited. Repeatedly dequeue, then enqueue each unvisited neighbour. Mark on enqueue to avoid duplicates.
Grids are graphs
Each cell is a node; its up/down/left/right cells are neighbours. Flood fill and 'number of islands' are BFS/DFS on a grid.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
type Graph = Map<string, string[]>;
function addEdge(g: Graph, a: string, b: string): void {
if (!g.has(a)) g.set(a, []);
if (!g.has(b)) g.set(b, []);
g.get(a)!.push(b);
g.get(b)!.push(a); // undirected
}
// Shortest number of edges from start to every reachable node.
function bfs(g: Graph, start: string): Map<string, number> {
const dist = new Map<string, number>([[start, 0]]);
const queue = [start];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
for (const next of g.get(node) ?? []) {
if (dist.has(next)) continue;
dist.set(next, dist.get(node)! + 1);
queue.push(next);
}
}
return dist;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| BFS / DFS | O(V + E) | O(V) |
| Adjacency list space | — | O(V + E) |
| Adjacency matrix space | — | O(V²) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Number of islands
Write num_islands(grid) where grid is a 2-D array of '1' (land) and '0' (water). Count groups of land connected horizontally or vertically.