BFS in Graphs
Walk a graph outwards from one node in layers of equal distance, with a queue and a visited stamp.
Examples
Two paths reach it: 0 → 2 directly, and 0 → 1 → 2.
0 and 5 lie in different components, so the queue empties first.
Problem Understanding
Given n nodes numbered 0 to n - 1 and a list of undirected edges, decide whether a path runs from source to destination (LeetCode 1971).
- Input:
n = 3,edges = [[0,1],[1,2],[2,0]],source = 0,destination = 2. - Output:
true— 0 and 2 are joined directly.
A graph is not a tree: it can hold cycles (0 → 1 → 2 → 0), several routes to the same node, and parts that are not joined at all. That is why BFS on a graph needs the one thing a tree traversal can do without — a record of what it has already seen.
BFS answers the yes/no question, and on the way it answers a stronger one for free: because it leaves the source in layers, the distance it records for each node is the fewest edges from the source.
Algorithm Strategy
Walk outwards from the source, one layer at a time.
- Adjacency list: one list of neighbours per node, with every edge added to both of its ends, because the edges are undirected.
dist, doing two jobs:-1means "not discovered"; any other value is the number of edges from the source. One array is both the visited set and the distances.- Queue: start with the source, stamped
dist = 0. - Loop: dequeue a node. If it is the destination, return
true. Otherwise take each neighbour in turn — one that is already stamped is skipped, and a new one is stampeddist[node] + 1and joins the back of the queue. - Queue empty: nothing further is reachable, so return
false.
Stamp on enqueue, not on dequeue. If a node were marked only as it came out of the queue, every neighbour that met it first would enqueue its own copy, so the queue would fill with duplicates and the work would grow with the edges into each node. Stamping as it goes in means each node enters exactly once.
Interactive Visualization
dN = EDGES FROM THE SOURCE · GREEN RING = DESTINATION · GREEN EDGES = HOW EACH NODE WAS FIRST REACHED
BUILD LISTS
0 → 5
—
stamped
0
Answer
—
queue (front first)
Empty
layers
Nothing stamped yet
Build the adjacency list: 6 empty lists, then each of the 6 edges added to both ends
Next
Enqueue the source, 0, and stamp it dist 0 — every other node is still -1
edges
n
source
destination
Legend & Complexity
The node just dequeued
Stamped and waiting in the queue
Dequeued and finished — dN is its distance from the source
The destination, before the search reaches it
Time
O(V + E)
Space
O(V + E)
BFS from source to destination on LeetCode 1971. The number above a node is its stamp — the edges from the source — and the queue beside the figure never holds more than two of those values at once, which is exactly why the first time BFS reaches a node is by a shortest route. Green edges are the ones the search actually arrived by. Try the Cycle preset to watch already-stamped nodes being skipped.
Dry Run
Graph: n = 6, edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]], source = 0, destination = 5.
| Dequeued | Its stamp | Neighbours | Stamped now | Queue after |
|---|---|---|---|---|
| 0 | 0 | 1, 2 | 1 and 2, both at 1 | [1, 2] |
| 1 | 1 | 0, 3 | 3, at 2 (0 is already stamped) | [2, 3] |
| 2 | 1 | 0, 3 | none — both are stamped | [3] |
| 3 | 2 | 1, 2, 4 | 4, at 3 | [4] |
| 4 | 3 | 3, 5 | 5, at 4 | [5] |
| 5 | 4 | — | it is the destination — return true |
— |
5 comes out of the queue stamped 4, and 0 → 1 → 3 → 4 → 5 is indeed four edges. Notice the queue on every row: it holds one layer, or two neighbouring ones, and never more.
Edge Cases & Common Mistakes
Edge Cases:
source == destination: returntruebefore the graph is even built — LeetCode counts the empty path.- Disconnected graph: the queue empties with the destination never stamped, which is the
falsecase. - Cycles: the
dist[neighbor] != -1check is the whole reason the walk cannot go round for ever. - No edges at all: every node but the source stays at -1.
Common Mistakes:
- Marking a node visited when it is dequeued rather than when it is enqueued, which lets the same node into the queue several times over.
- Adding an undirected edge to one end only, so half the graph is unreachable.
- Using a list and
pop(0)(orshift()) as the queue: that is O(n) per dequeue, and it turns an O(V + E) search into a quadratic one.
Solution Template
BFS out from the source, stamping each node with its distance on the way (LeetCode 1971).
BFS in Graphs Code
1var validPath = function(n, edges, source, destination) {2 if (source === destination) {3 return true;4 }5 const graph = Array.from({ length: n }, () => []);6 for (const [u, v] of edges) {7 graph[u].push(v);8 graph[v].push(u);9 }10 const dist = new Array(n).fill(-1);11 dist[source] = 0;12 const queue = [source];13 let head = 0;14 while (head < queue.length) {15 const node = queue[head++];16 if (node === destination) {17 return true;18 }19 for (const neighbor of graph[node]) {20 if (dist[neighbor] !== -1) {21 continue;22 }23 dist[neighbor] = dist[node] + 1;24 queue.push(neighbor);25 }26 }27 return false;28};