cf.completefrontend
GRAPHS · CORE

Breadth-first search (BFS)

Explore a graph in rings around the start, all nodes 1 step away, then 2 steps, and so on, which gives the fewest steps to every node.

Time O(n + e)Space O(n)10 practice problemsStep-through picture

The idea

Breadth-first search, or BFS, visits the nodes of a graph in order of how many edges away they are from a start node. First the start itself, then every neighbor (1 step away), then every neighbor of those neighbors (2 steps away), and so on.

It does this with a queue: a line where the first one in is the first one out. Nodes join the back of the queue when they are discovered and are handled from the front. Because nodes 1 step away join before nodes 2 steps away, they are also handled first.

This order gives BFS its best power. The first time BFS reaches a node, it has found a shortest path to it, counted in edges. That's why BFS answers "what is the fewest number of clicks, moves, or hops?" whenever every edge costs the same.

An everyday example

A rumor spreading in an office

One person hears some news at 9:00. By 9:01 they have told everyone at their desk cluster. By 9:02 each of those people has told everyone at their own clusters, and so on. If you write down the minute each person first heard the news, you get each person's distance from the first one. Nobody who already knows gets told again.

How the example maps to the code
In the exampleIn the code
The first person who hears the newsstart, with dist[start] = 0
People waiting to pass the news onThe queue
The minute someone first hears itdist[next] = dist[node] + 1
Ignoring people who already knowif (dist[next] !== -1) continue

From the slow way to breadth-first search (bfs)

  1. Say you need the fewest edges from start to every node. The obvious way is to try every path from start, measure each one, and keep the shortest per node. The number of paths can explode: a 10 by 10 grid already has far more paths between two corners than any computer can list.
  2. Look at the distances more closely. The nodes 1 step away are exactly the neighbors of start. The nodes 2 steps away are the neighbors of those nodes that weren't already found. In general, ring d + 1 is every not-yet-found neighbor of ring d. So distances can be built ring by ring, without ever listing paths.
  3. That only works if every node of ring d is handled before any node of ring d + 1. A queue gives that order for free. Nodes found while handling ring d join the back, behind the rest of ring d, so they come out later.
  4. Finally, record a node's distance the moment it is first found and never change it. Then each node joins the queue once and each neighbor list is read once, so the work is n + e. That loop is breadth-first search.

How it works

  1. Make dist, one number per node, all -1, which means "not reached yet".
  2. Set dist[start] = 0 and put start in the queue.
  3. Take the node at the front of the queue. The loop uses an index, head, instead of shift(), so taking from the front is fast.
  4. Look at each neighbor next of node. If dist[next] is not -1, it was already reached by a path at least as short, so skip it.
  5. Otherwise set dist[next] = dist[node] + 1 and add next to the back of the queue.
  6. When the queue is used up, dist holds the fewest edges from start to every node, and -1 for nodes that can't be reached.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function bfs(graph, start) {
  2. const dist = new Array(graph.length).fill(-1);
  3. dist[start] = 0;
  4. const queue = [start];
  5. for (let head = 0; head < queue.length; head++) {
  6. const node = queue[head];
  7. for (const next of graph[node]) {
  8. if (dist[next] !== -1) continue;
  9. dist[next] = dist[node] + 1;
  10. queue.push(next);
  11. }
  12. }
  13. return dist;
  14. }

How fast it is

TimeO(n + e)
Extra memoryO(n)

Every node enters the queue at most once and every edge is looked at once from each end. dist and the queue hold at most n entries.

  • Best caseO(n)

    start has no neighbors. The loop runs once, but filling dist still costs n steps.

  • Average caseO(n + e)

    Every node in the start's part of the graph is pushed once, and its neighbor list is read once.

  • Worst caseO(n + e)

    The whole graph is connected to start, so every node and every edge is touched. Each undirected edge is checked twice, once from each end.

Common mistakes

  • Using queue.shift() in a loop. Each call moves every other item, so a big graph becomes slow. Keep a head index instead.
  • Marking a node as seen only when it leaves the queue. The same node gets added many times. Mark it when you add it.
  • Using BFS when edges have different weights. BFS counts edges, not total weight; use Dijkstra's algorithm instead.
  • Forgetting nodes that can't be reached. Decide what to return for them, such as -1, and test a graph with two separate parts.

When to use it

Look for these clues in a problem:

  • The question asks for the fewest steps, moves, clicks, hops, or edges.
  • Every move costs the same, or there are no weights at all.
  • You need nodes grouped by distance: everyone 1 step away, then 2 steps away.
  • The graph might be large, and you want to stop as soon as you reach a target.

Check yourself

Answer each one in your head first, then open it.

Why mark a node when it is pushed instead of when it is taken out?

If you mark it only when it leaves, every neighbor that sees it before then pushes it again. In a dense graph the queue can grow to about e entries instead of n.

What goes wrong if you swap the queue for a stack but keep everything else?

All reachable nodes still get a number, but not the shortest one. With edges 0-1, 0-2, 2-4, 4-3, 1-3, a stack gives dist[3] = 3, while BFS correctly gives 2.

At most how many different distance values are in the queue at one time?

Two: some nodes at distance d in front and some at d + 1 behind them. That is why nodes leave the queue in order of distance.

In the trace, why didn't node 0 change dist[6]?

6 already had distance 2 from node 5. Reaching it through 0 would also be 2, so the first value is kept and 6 isn't pushed twice.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 10 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

BFS keeps two promises. First, the nodes waiting in the queue, read from head to the end, have distances that never go down, and the first and last differ by at most 1. Second, every distance already written in dist is the true fewest number of edges from start.

Handling a node keeps both promises. Suppose node has true distance d and a neighbor next is still -1. Its true distance is at most d + 1, because of the edge. It can't be smaller: then the node before it on a shortest path would have distance d - 1 or less, would have left the queue before node, and would already have set dist[next]. So d + 1 is exact, and it goes behind the other nodes, which are all d or d + 1.

The loop ends because each node is pushed at most once: dist stops being -1 at the moment of the push, so it can't pass the check again. And no reachable node is missed. On a path from start to any reachable node, a first unreached node would follow a reached one, but every reached node gets handled and would have reached it.

Going deeper

3 more ideas

Why the first visit is the shortest

The queue always holds nodes from at most two rings: some at distance d at the front and some at distance d + 1 behind them. A node at distance d + 2 can only be added while a d + 1 node is handled, which happens after every d node. So nodes come out of the queue sorted by distance, and the first time a node is reached, it is reached from the closest possible node.

Why it takes O(n + e) time

Each node enters the queue at most once, because it is marked in dist the moment it is added. When a node leaves the queue, the loop reads its neighbor list once. Over the whole run that reads every edge once (twice for undirected graphs). So the work is the number of nodes plus the number of edges.

Mark when you add, not when you remove

Set dist[next] at the moment next joins the queue. If you only mark nodes when they leave the queue, the same node can be added many times by different neighbors, and the queue can grow far beyond n.

Work it by hand

Every step in a table, with why

Fewest edges from node 2 in an undirected graph with 7 nodes. Nodes 1 and 4 are only connected to each other.

graph = [[2, 6, 3], [4], [5, 0], [6, 0], [1], [2, 6], [5, 0, 3]], start = 2

StepnodeNeighbors checkeddistqueue waitingWhat happensWhy
1--[-1, -1, 0, -1, -1, -1, -1][2]Start at 2Every node is -1, not reached, except the start, which is 0 steps from itself.
225 new, 0 new[1, -1, 0, -1, -1, 1, -1][5, 0]Ring 1 is foundBoth neighbors of 2 get distance 0 + 1 = 1 and join the back of the queue.
352 skip, 6 new[1, -1, 0, -1, -1, 1, 2][0, 6]dist[6] = 22 already has a distance, so it is skipped. 6 is new and is one step further than 5.
402 skip, 6 skip, 3 new[1, -1, 0, 2, -1, 1, 2][6, 3]dist[3] = 26 was already reached from 5 with distance 2. Going through 0 would also give 2, a tie, so nothing changes.
565, 0, 3 all skipsame[3]Nothing newEvery neighbor of 6 already has a distance at least as small as 2 + 1.
636 skip, 0 skipsame[]Nothing newThe last node of ring 2 finds nothing new either.
7--[1, -1, 0, 2, -1, 1, 2][]head reached the end: stophead equals queue.length, so the loop ends and dist is returned.

It returns [1, -1, 0, 2, -1, 1, 2]. Five nodes passed through the queue and 12 neighbor checks were made, two for each of the 6 edges in the start's part of the graph. Nodes 1 and 4 stay -1 because no edge leads to them.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Breadth-first search (BFS)O(n + e)O(n)You need the fewest edges or moves, and every edge counts the same.
Depth-first searchO(n + e)O(n)You only need to know what is reachable, or you need finish order for things like topological sort. Its paths are not shortest.
Dijkstra's algorithmO(e log n)O(n + e)Edges have different non-negative costs and you need the cheapest total, not the fewest edges.
Floyd-WarshallO(n³)O(n²)You need the distance between every pair of nodes and n is only a few hundred.

Extra memory: O(n): dist holds n numbers and the queue holds at most n nodes, because each node is pushed once. The adjacency list itself is the input.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Breadth-first search (BFS) and the other approaches, on a scale where each line up is 10 times more steps.
  • Breadth-first search (BFS), Depth-first search O(n + e)
  • Dijkstra's algorithm O(e log n)
  • Floyd-Warshall O(n³)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Breadth-first search (BFS)202,0002 million
Depth-first search202,0002 million
Dijkstra's algorithm339,96620 million
Floyd-Warshall1,0001 billionmore than a quadrillion

Inputs that need care

5 tricky inputs
start has no edges
The loop handles start, finds an empty list, and ends. Every other node stays -1.
A graph in two pieces, as in the trace
Nodes in the other piece are never pushed and stay -1. Decide what the problem wants for them, such as -1 or Infinity, and test it.
A directed graph where x can reach start but start can't reach x
BFS only follows edges forward, so dist[x] stays -1. To get distances to start, run BFS on the reversed graph.
Self-loops or repeated edges
The dist[next] !== -1 check skips them, so they cost a little time and change nothing.
You only need the distance to one target
Return dist[next] as soon as next === target is set. That distance is already final, and the rest of the graph isn't explored.

Variations and follow-ups

Twists interviewers add

Level by level

Before handling the queue, read its current length and handle exactly that many nodes. Each batch is one ring, which is handy for "after how many minutes?" questions or for grouping nodes by distance.

Rebuilding the path

Keep a parent array and set parent[next] = node when next is first reached. Walking parent back from a target and reversing gives one shortest path.

Many starts at once

Put several start nodes in the queue at distance 0. One BFS then gives each node its distance to the nearest start. That is multi-source BFS.

When edges have costs

BFS counts edges, not costs. If every cost is 0 or 1, use 0-1 BFS with a deque. For other non-negative costs, use Dijkstra's algorithm with a heap.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "fewest", "minimum number of steps", "shortest" with no weights, or "nearest". If moves have different costs, it is not plain BFS.
  • Say the key rule out loud: "I mark a node when I add it to the queue, so each node enters once and the first distance is the shortest". Interviewers listen for that.
  • Test by hand on a graph with an unreachable node and on start === target. Both are where answers like -1 and 0 come from.
  • Expect "can you return the path, not just its length?". Keep a parent array, then walk back from the target. Also expect "why not shift()?": it copies the array, which makes big inputs slow.

Where frontend code uses it

The same idea in real UI code
  • Finding the fewest clicks between two pages of a site from its link graph, or the shortest chain of redirects.
  • Walking the DOM level by level, for example to find the nearest matching element below a node before looking deeper.
  • Social features such as "people you may know", which look at users exactly 2 steps away in the follow graph.

Related algorithms