Skip to content

level 7 · Graphs

Breadth-First Search

Explore a network in rings, nearest first — using a queue.

11 min 95 XP

what is it

Start here

A graph is just dots joined by lines — cities joined by roads, people joined by friendships, web pages joined by links. Breadth-first search is how you explore one without getting lost or going in circles.

BFS explores in rings. It visits everything one step from the start, then everything two steps away, then three. It never rushes ahead — it finishes a whole ring before starting the next.

The engine that makes this happen is a queue. Newly found nodes join the back of the line; you always take the next node from the front. Because a queue is first-in-first-out, closer nodes are always served before farther ones. Watch the queue on the right fill and drain — that ordering is the whole trick.

This 'nearest first' behaviour is why BFS finds the shortest path in an unweighted graph. The first time it reaches a node, it has arrived by the fewest possible steps — it couldn't have gotten there sooner.

real-life analogy

Picture it

A rumour spreading through a room

You tell the people right next to you. They tell the people next to them. The rumour moves outward one ring at a time — everyone one handshake away hears it before anyone two handshakes away. That expanding circle is exactly a breadth-first search.

interactive visualization

Watch it run

Pick a start node: 1 = A, up to 8 = H. Watch it explore in rings.

A
B
C
D
E
F
G
H

queue · FIFO

A

take from the front

Breadth-first search fans out in rings from A, using a queue. A queue is first-in-first-out, so nearer nodes always come off before farther ones — that's why BFS explores level by level.

step 01/21

  • just discovered
  • visited
  • visiting now
1function bfs(graph, start) {
2 const queue = [start];
3 const seen = new Set([start]);
4 while (queue.length > 0) {
5 const node = queue.shift();
6 visit(node);
7 for (const next of graph[node]) {
8 if (!seen.has(next)) {
9 seen.add(next);
10 queue.push(next);
11 }
12 }
13 }
14}

variables right now

start
A
queue
A
comparisons 0moves 0

the dry run · every step, in words

21 steps

complexity

What it costs

best case
O(V + E)
average
O(V + E)
worst case
O(V + E)
extra memory
O(V)

It touches every node (V) once and looks along every edge (E) once, so the cost is V + E. The space is the queue plus the 'seen' set, which in the worst case holds every node: O(V).

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Forgetting to mark nodes as seen when you add them to the queue.

    Mark a node the moment it enters the queue, not when you visit it. Otherwise the same node gets queued many times and you may loop forever on a cycle.

  • Using a stack instead of a queue.

    A stack turns BFS into DFS — it goes deep instead of wide. If you want rings, you need first-in-first-out: a queue.

  • Checking 'seen' only when popping, not when pushing.

    Too late — the duplicates are already in the queue. Check and mark before pushing, so a node can only ever be added once.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+95 XP

01What data structure drives breadth-first search?

02In an unweighted graph, what does BFS find?

03Why must you mark a node 'seen' as soon as it enters the queue?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.