Algorithms · BFS

Breadth-first search

Searching in rings, why BFS finds the shortest path, BFS on a grid, multi-source BFS, 0-1 BFS, bidirectional BFS, and when to reach for DFS instead.

Updated 2026-09-21

On this page

BFS is the algorithm you use when the question is how far. It explores a graph in rings: everything one step away, then everything two steps away, and so on. That single habit is what makes it find the shortest path without doing anything clever — and it is why so many puzzle-shaped problems turn out to be BFS in disguise.

The map

Read this first when short on time. Every branch is a section below.

Figure 1. The whole article on one page. Every branch is a section below; fold what you know, open what you do not.

The idea: search in rings

Imagine dropping a stone in water. The ripple reaches everything one metre away before it reaches anything two metres away. BFS does exactly that on a graph.

Start at one node. Visit all of its neighbours — that is ring 1. Then visit all of their unvisited neighbours — ring 2. Keep going until there is nothing new to see.

Figure 2. BFS from A. Everything in a column is the same distance from the start, and BFS finishes a whole column before touching the next one.

The useful consequence is right there in the picture: a node in ring k is exactly k steps from the start. BFS does not compute distances as a separate step — the order it visits things is the distance.

In the wild

Shortest route with equal-cost steps — the fewest stops on a metro line, the fewest moves in a puzzle, the fewest hops between routers.
Degrees of separation — how many introductions away two people are on a social network is a BFS from one of them.
Web crawlers start from seed pages and explore outward in rings, so the pages closest to the seeds are fetched first.

The algorithm

Three pieces: a queue of nodes waiting to be explored, a visited set so nothing is processed twice, and somewhere to record the answer — usually a distance or a parent per node.

Start. Put the starting node in the queue and mark it visited, at distance 0.
Take the front. Remove the node at the front of the queue. This is the closest unexplored node.
Look at its neighbours. For each one not yet visited: mark it visited, set its distance to the current node's distance plus one, and put it at the back of the queue.
Repeat until the queue is empty, or until you take out the node you were looking for.

from collections import deque

def bfs(graph, start):
    dist = {start: 0}          # doubles as the visited set
    q = deque([start])

    while q:
        node = q.popleft()                 # front: the closest unexplored node
        for nxt in graph[node]:
            if nxt not in dist:            # not seen before
                dist[nxt] = dist[node] + 1
                q.append(nxt)              # back: one ring further out
    return dist

Running that on Figure 2 gives this trace. Watch how the queue always holds at most two rings at a time — the tail of the current one and the head of the next.

Step	Taken from front	Newly added	Queue after
1	A	B, C, D	B C D
2	B	E	C D E
3	C	F	D E F
4	D	G	E F G
5	E	— (F already seen)	F G
6	F	H	G H
7	G	— (H already seen)	H
8	H	—	empty, done

Watch out

Mark a node visited when you push it, not when you pop it. If you wait until popping, a node with three neighbours pointing at it gets pushed three times, the queue fills with duplicates, and on a big graph it can blow up. This is the single most common BFS bug.

Cost. Every node enters the queue once and every edge is looked at once, so the time is O(V + E) — nodes plus edges. Memory is O(V) for the visited set, plus the queue, which at its widest holds one whole ring.

Why it finds the shortest path

This is the property worth understanding rather than memorising, because it also tells you exactly when BFS stops being correct.

The queue is first-in-first-out, and nodes enter it in order of distance: all the distance-1 nodes go in before any distance-2 node. So they also come out in that order. When BFS first reaches a node, every shorter route has already been tried and failed — which means the first time you see a node, you have seen it by a shortest route. There is no way to find it again more cheaply later, so a node never needs to be updated once set.

That argument leans entirely on one assumption: every edge costs the same. One step is one step. The moment edges have different weights, a two-edge route can be cheaper than a one-edge route, "rings" stop matching "distance", and BFS gives the wrong answer. That is the job of Dijkstra's algorithm, which replaces the queue with a priority queue that always takes the cheapest node rather than the earliest.

To recover the actual path and not just its length, store a parent for each node as you discover it, then walk the parents backwards from the target and reverse the list.

parent = {start: None}
# ... inside the loop, when you first see nxt:
#     parent[nxt] = node

def path_to(target, parent):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]          # reverse: start ... target

BFS on a grid

Most BFS problems in practice are grids — a maze, a map, an image. The nice part is that there is no graph to build: a cell is a node, and its neighbours are simply the cells up, down, left and right.

Figure 3. BFS on a grid. The numbers are simply the ring each cell landed in, so reading the distance to any cell is free once the pass is done.

from collections import deque

def grid_bfs(grid, start):
    rows, cols = len(grid), len(grid[0])
    sr, sc = start
    dist = [[-1] * cols for _ in range(rows)]
    dist[sr][sc] = 0
    q = deque([(sr, sc)])

    while q:
        r, c = q.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols \
               and grid[nr][nc] != '#' and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

Three things to get right every time: stay inside the bounds, skip walls, and check that the cell has not already been given a distance. Here dist[nr][nc] == -1 is doing double duty as the visited check, which is why there is no separate set.

Multi-source BFS

Now the variant that looks hard and is almost free. The question changes from "how far is everything from this cell" to "how far is everything from the nearest of these cells".

The obvious approach is to run BFS once per source and keep the minimum, which costs sources × (V + E). The trick is that you do not need to. Put every source in the queue before you start, all at distance 0. That is the entire change.

Figure 4. Multi-source BFS. Seeding the queue with every source makes the rings grow from all of them at once, and each cell is claimed by whichever ring reaches it first — which is its nearest source.

q = deque()
for (r, c) in sources:      # the ONLY difference
    dist[r][c] = 0
    q.append((r, c))

# ... exactly the same loop as before

Why is it still correct? Because the queue is still sorted by distance. All the 0s are in front, so all the 1s get added before any 2 — the rings just happen to have several centres. And because a cell is claimed the first time it is reached, it is claimed by whichever source got there first, which is the nearest one.

The cost is still O(V + E) for the whole thing, not per source. Once you recognise this shape, a lot of problems collapse into it:

Problem	Sources	Answer
Rotting oranges — how long until all fruit rots	Every already-rotten orange	The largest distance reached
Nearest exit from a maze	Every exit cell	The distance at your position
Distance to the nearest water on a map	Every water cell	The whole distance grid
Walls and gates	Every gate	The whole distance grid

Tip

The tell for multi-source BFS is the word nearest in the problem, with more than one thing you could be near. If you catch yourself about to loop over sources running a BFS each time, stop and seed the queue instead.

Two more variants worth knowing

Both are small changes to the same loop, and both show up often enough to recognise.

0-1 BFS: when edges cost 0 or 1

Sometimes moves are not all equal, but there are only two prices — a free move and a costly one. Breaking a wall costs 1, walking costs 0. Changing direction costs 1, continuing costs 0.

Full Dijkstra would work but is heavier than necessary. Instead use a double-ended queue: a free edge pushes to the front, a costly edge pushes to the back.

flowchart TD
  N["take the node at the front of the deque"] --> E{Edge weight?}
  E -- "0, free" --> F["push the neighbour to the FRONT"]
  E -- "1, costs a step" --> B["push the neighbour to the BACK"]

Figure 5. 0-1 BFS, one iteration of the loop. Free moves jump the queue, so the deque stays sorted by distance exactly as a plain BFS queue does — with the same O(V + E) cost.

The deque stays sorted by distance because a free move keeps you in the current ring, so it belongs at the front with the rest of that ring, while a costly move puts you in the next ring, at the back.

Bidirectional BFS: search from both ends

If you know both the start and the target, you can run two searches — one from each — and stop when they meet.

The reason this helps is that a ring grows fast. If each node has about 10 neighbours, a search 6 steps deep touches roughly 10⁶ nodes. Two searches of 3 steps each touch about 10³ nodes apiece — a thousand times less work for the same answer.

flowchart TD
  S["start"] --> A["rings grow outward"]
  G["target"] --> B["rings grow outward"]
  A --> M["the two frontiers touch"]
  B --> M
  M --> P["path length = steps from each side, added"]

Figure 6. Bidirectional BFS. Two small searches replace one large one, which is why word-ladder and puzzle-state problems use it.

The catch is that you must know the target in advance, so it does not apply when you are mapping distances to everything. Expand whichever frontier is currently smaller, and keep a visited set per side so you can tell when they overlap.

BFS or DFS?

They visit the same nodes and cost the same. The difference is the order, and the order is the whole point.

	BFS	DFS
Structure	Queue — first in, first out	Stack, or recursion
Order	Closest first, ring by ring	One path to the end, then back up
Shortest path	Yes, when steps cost the same	No
Memory	One whole ring, which can be wide	One path, which is usually shallower
Good for	Fewest steps, level-by-level work, answers likely close by	Cycle detection, topological sort, exploring every path, backtracking

The memory row is the practical one. On a wide graph — a grid, a social network — the widest ring can be enormous, and BFS has to hold all of it. DFS only ever holds the current path. If you need the shortest path, pay for it; if you just need to reach everything, DFS is cheaper.

Recap

BFS explores in rings: everything one step away, then everything two steps away. A node in ring k is exactly k steps from the start.
Three pieces: a queue, a visited set, and a record of distance or parent. Take from the front, push neighbours to the back.
Mark a node visited when you push it, not when you pop it — otherwise it enters the queue several times.
The first time BFS reaches a node, it has reached it by a shortest route, because nodes leave the queue in order of distance.
That guarantee needs every edge to cost the same. With different weights, use Dijkstra instead.
Store a parent per node to rebuild the actual path, then walk parents backwards and reverse.
On a grid there is no graph to build: a cell is a node and its neighbours are up, down, left and right. Check bounds, skip walls, and check the distance is unset.
Multi-source BFS: push every source at distance 0 before the loop starts. That is the only change.
It is correct because the queue stays sorted by distance, and each cell is claimed by whichever ring reaches it first — its nearest source.
Multi-source costs one traversal, not one per source, and the word "nearest" in a problem is usually the tell.
0-1 BFS handles edges that cost 0 or 1 with a deque: free moves to the front, costly moves to the back.
Bidirectional BFS searches from both ends and stops when the frontiers meet, turning one deep search into two shallow ones.
Time is O(V + E) for all of these. Memory is the widest ring, which is where BFS loses to DFS.

Questions

Try answering each one out loud before opening it. Lead with the one-line answer, then the reasoning, then one detail that shows depth.

Explain BFS in one or two sentences.

BFS explores a graph in rings from a starting node: everything one step away, then everything two steps away, using a queue so that the closest unexplored node is always processed next.

The visit order is the distance order, so distances come out for free.
A queue is what produces the ring behaviour — first in, first out.
A visited set stops the same node being processed twice.

Every other property, including the shortest-path guarantee, follows from that ordering rather than from any extra work.

Why does BFS find the shortest path?

Because nodes enter the queue in order of distance and it is first-in-first-out, so they come out in that order too — which means the first time you reach a node, every shorter route has already been tried.

No later discovery can be shorter, so a node's distance never needs updating.
The guarantee holds only when every edge counts as one step.
With different edge weights, a longer route can be cheaper, and BFS gives the wrong answer.

Dijkstra's algorithm is the repair: it swaps the queue for a priority queue that always takes the cheapest node rather than the earliest.

Why mark a node visited when you push it rather than when you pop it?

Because between being pushed and being popped, the same node can be discovered by several other neighbours and pushed again — so marking late lets duplicates pile up in the queue.

A node with many incoming edges could enter the queue once per neighbour.
The distance would still come out right, but memory and time can blow up badly on a dense graph.
Marking on push keeps the invariant that each node enters the queue exactly once.

It is the most common BFS bug, and it usually passes small tests before failing on a large input.

What are the time and space costs?

O(V + E) time, because every node is dequeued once and every edge examined once, and O(V) space for the visited and distance records plus the queue.

The queue's peak size is the widest ring, which on a grid or a dense graph can be very large.
On a grid with R rows and C columns that is O(R × C), since each cell has at most four edges.
DFS has the same time cost but holds only one path, which is usually much less memory.

Memory, not time, is the reason to prefer DFS when the shortest path is not needed.

How do you turn a grid into a graph for BFS?

You do not build one: a cell is a node and its neighbours are the cells up, down, left and right, computed on the fly from the coordinates.

The three checks are bounds, walls, and whether the cell already has a distance.
The distance array doubles as the visited set, so no separate structure is needed.
Diagonal movement just means eight offsets instead of four.

This implicit-graph idea generalises: any state with well-defined moves — puzzle positions, word transformations — can be searched without materialising the graph.

What is multi-source BFS and why is it correct?

Push every source into the queue at distance 0 before the loop starts, so rings grow from all of them simultaneously; it is correct because the queue is still sorted by distance, just with several centres.

All the 0s are dequeued before any 1, so all the 1s are added before any 2.
A cell is claimed the first time it is reached, which is by whichever source is nearest.
The loop body is completely unchanged — only the initialisation differs.

It is one of the largest gains available for one line of code, turning sources × (V + E) into a single V + E pass.

Given a grid of rotting and fresh oranges, how long until everything rots?

Multi-source BFS with every already-rotten orange as a source; the answer is the largest distance reached, and if any fresh orange still has no distance at the end, it can never rot.

Each BFS ring is one minute of time passing.
Seeding all rotten cells at once models them spreading simultaneously, which is what the problem describes.
Running a separate BFS per rotten orange would be far slower and no more correct.

Recognising that "everything spreads at once" means "seed the queue with everything" is the whole insight.

How would you find the nearest exit from your position in a maze?

Run multi-source BFS from all the exits at once and read the distance at your own cell — one pass answers it, and the same grid answers it for every other starting position too.

Searching from your position instead would also work, stopping at the first exit found.
Seeding from the exits is better when many positions need answering, since the grid is computed once.
Seeding from your position is better when there is one query and exits are far away.

Choosing which end to search from is a real decision: search from the side with fewer sources, or the side that answers more questions.

When does 0-1 BFS apply, and how does it work?

When every edge costs either 0 or 1 — a free move and a costly one. Use a deque: push a 0-cost neighbour to the front and a 1-cost neighbour to the back.

A free move stays in the current ring, so it belongs with that ring at the front.
A costly move belongs to the next ring, so it goes to the back.
The deque stays sorted by distance, keeping the cost at O(V + E) rather than Dijkstra's log factor.

Typical uses are grids where breaking a wall costs one, or where turning costs one and going straight is free.

Why is bidirectional BFS so much faster, and when can you not use it?

Because the number of nodes in a ring grows exponentially with depth, so two searches of half the depth explore dramatically fewer nodes than one full-depth search — with a branching factor of 10 and a depth of 6, roughly a thousand times fewer.

It needs a known target, so it cannot be used to compute distances to everything.
Expand whichever frontier is currently smaller to keep the saving.
Each side needs its own visited set so you can detect the overlap.

Word ladders and puzzle-state searches are the classic cases, because the state space branches widely but the answer is only a few moves deep.

When would you choose DFS over BFS?

When you do not need the shortest path: cycle detection, topological sorting, exploring every path, or any backtracking problem — and whenever memory is tight, since DFS holds one path rather than a whole ring.

Both visit every node and edge, so the time cost is the same.
On a wide graph, BFS's widest ring can be enormous while DFS stays shallow.
DFS is also natural to write recursively, which makes some problems much shorter.

The one thing DFS cannot give you is the fewest steps, which is the only reason to pay BFS's memory cost.

How do you count levels, for example the depth of a tree, with BFS?

Process the queue one full level at a time: record its length before the inner loop, dequeue exactly that many nodes, and increment the depth once per outer iteration.

The queue holds exactly one complete level at the start of each outer pass.
This is the standard level-order traversal, and it also gives you each level as a list.
The alternative is storing a depth alongside every queued node, which uses slightly more memory but avoids the nested loop.

Both are common; the level-size version is preferred when the problem asks for something per level rather than per node.