What Is Breadth-First Search in Programming? A Guide

If you are asking what is breadth-first search in programming?, the short answer is this: it is a way to explore a graph or a grid by visiting everything one step away first, then everything two steps away, then three, and so on. It spreads out from the start like a ripple in water. Because of that, it finds the shortest path when every step costs the same.

What is breadth-first search in programming?

Breadth-first search, usually shortened to BFS, is an algorithm for walking through connected things. Those things can be cities joined by roads, web pages joined by links, people joined by friendships, or tiles on a game map. Programmers call the things nodes and the connections edges.

BFS answers two common questions:

• Can I get from node A to node B at all?
• What is the fewest number of steps to get there?

The word "breadth" is the clue. You go wide before you go deep. You finish every node at distance 1 before you touch any node at distance 2.

How breadth-first search works step by step

1. Put the start node in a waiting line. Mark it as seen.
2. Take the node at the front of the line.
3. Look at its neighbors. For each neighbor you have not seen, mark it as seen and add it to the back of the line.
4. Repeat from step 2 until the line is empty or you find the node you wanted.

The "seen" mark matters. Without it, you would walk in circles forever on any graph that has a loop. With it, each node enters the line at most once.

To get the shortest path, not just a yes or no, remember where each node came from. When you reach the goal, follow those stored links backward to the start.

The waiting line is a queue: first in, first out. That rule is what makes the search breadth-first.

The start goes in first. Its neighbors go in next, so they come out next. Their neighbors go in behind them, so those come out after all the distance-1 nodes are done. The line stays sorted by distance with no extra work from you.

If you swap the queue for a stack (last in, first out), the same loop becomes depth-first search. One data structure decides the whole behavior.

Breadth-first search code example in Python

Here is a small version that finds the fewest steps between two nodes. The graph is a dictionary that maps each node to a list of its neighbors. Read it line by line:

• from collections import deque gives you a queue that is fast at both ends.
• queue = deque([(start, 0)]) puts the start in the line with a distance of 0.
• seen = {start} records that the start has been visited.
• while queue: keeps going until the line is empty.
• node, dist = queue.popleft() takes the front of the line.
• if node == goal: return dist stops on arrival. The first arrival is always the shortest, because closer nodes came out first.
• for nxt in graph[node]: loops over the neighbors, and if nxt not in seen: skips any already visited.
• seen.add(nxt) and queue.append((nxt, dist + 1)) mark the neighbor and put it at the back of the line, one step farther out.
• return None after the loop means the goal was never reachable.

Use deque, not a plain list with pop(0): removing from the front of a list is slow.

Time and space complexity of BFS

BFS visits each node once and looks at each edge once or twice. If V is the number of nodes and E is the number of edges, the time is O(V + E).

The space is O(V) in the worst case. The seen set can hold every node, and the queue can hold a large share of them at once. This is the main cost of BFS: it keeps a whole "frontier" in memory, and on a wide graph that frontier gets big.

A 13 by 13 map has 169 tiles, and BFS touches each at most once. The "seen" idea is the same instinct as remembering past results so you do not redo work, which our guide to memoization in programming covers in a different setting.

When to use BFS, and how it differs from depth-first search

Use BFS when you want the fewest steps and every step costs the same, when you want everything within a certain distance of a start (all friends within two hops), or when you only need to know whether two points are connected.

Do not reach for plain BFS when:

• Steps have different costs. A road that takes ten minutes and a road that takes one minute both count as one step to BFS. Use an algorithm built for weighted edges instead.
• The graph is huge and the goal is deep. The queue can grow past what your memory can hold.

Depth-first search (DFS) goes the other way. It picks a neighbor and keeps going down that path until it hits a dead end, then backs up and tries the next one.

• Order: BFS goes level by level. DFS goes as deep as it can first.
• Data structure: BFS uses a queue. DFS uses a stack, or recursion, which is a stack in disguise.
• Shortest path: BFS finds it when steps cost the same. DFS does not promise it.

In a building, BFS checks every room on the first floor, then the second. DFS walks into one room, opens every closet, then comes back.

Breadth-first search on a game grid: a worked example

Games are full of grids, so they are a natural home for BFS. Take a tiny map: a 5 by 5 grid where you start in the top-left tile and the goal is the bottom-right tile. Some tiles are walls.

Run BFS and the line fills like this. The start is at distance 0. Its open neighbors, right and down, are at distance 1. Their open neighbors are at distance 2. Walls are simply never added to the queue. When the goal comes off the front of the line, you know its distance, and the stored "came from" links give you the route.

Each number is how many steps the tile is from the start. BFS reaches every 1 before any 2, and the goal is 8 steps away.

For a grid, the neighbor list is just up, down, left and right, skipping walls and tiles off the edge. That is the only part you change from the generic code above.

Where a real game uses BFS: checking that an arena is fair

In Tank City Zero Day, every wave is a freshly generated arena, 13 by 13 tiles and a mirror image left to right. Random walls could seal a tank in, so the game checks each arena first.

The rule in its code is that an arena is fair when the three enemy gates on the top row and the player start can all reach the tiles beside the CPU core, going round silicon and coolant. Firewall counts as open for this check, because any tank can shoot through it.

That is a reachability question on a grid, and the game's check is a breadth-first search. It puts the open tiles beside the core in a queue and marks them seen. Then it takes a tile off the front, looks at the four tiles up, down, left and right, skips anything off the edge, already seen, or blocked by silicon or coolant, and queues the rest. It floods outward from the core. When the queue is empty it asks one question: did the flood touch all three gates and the player start? If not, the arena is unfair.

The flood starts from the target, not from each gate, so one search answers for every gate at once. It needs no distances, only seen marks: BFS is useful even when you only want "can I get there".

An unfair arena is drawn again from the next seed. The game tries up to 40 times and then falls back to one fixed plain arena of mirrored firewall blocks. The game's own tests also check 300 arenas (30 seeds across 10 waves) to make sure each one passes. Our post on hitboxes in video games covers how shots meet tanks in the same games.

Frequently asked questions

What is breadth-first search in simple words?

It is a way to explore connected things by checking everything one step away, then everything two steps away, and so on. It uses a queue to keep that order.

Does BFS always find the shortest path?

Yes, when every step costs the same. If steps have different costs, BFS can return a path with the fewest steps that is not the cheapest one.

Why does BFS need a "seen" set?

Without it, BFS can revisit the same node again and again on graphs with loops. The set makes sure each node enters the queue only once.

Is BFS faster than depth-first search?

Both run in O(V + E) time. They differ in which nodes they visit first and how much memory they use, not in basic speed.

Can I use BFS on a game map?

Yes. Treat each tile as a node and each open neighboring tile as an edge. BFS then gives you the shortest route in tiles and tells you whether a tile can be reached at all.

Get started

The best way to learn BFS is to write it twice: once on a small dictionary graph, then once on a grid with walls. Print the distance of each tile as it leaves the queue and watch the ripple spread. Then change the queue to a stack and see how the order flips.

If you want a grid to look at while you think, open Tank City Zero Day and play a few waves: every arena you see passed a flood-fill check first. It plays in your browser on a computer or a phone and needs no account. Its sister game, Tank City Reboot, is the classic stage version.