Breadth-First Search
Breadth-First Search (BFS) explores a graph or tree outward in concentric layers, using a queue to process nodes in the order they are discovered.
Rings, Not Branches
Breadth-first search explores a graph by distance from a starting vertex. It visits everything one edge away, then everything two edges away, and so on — expanding outward in complete rings rather than following any single path.
The mechanism is a queue. Enqueue the source; then repeatedly dequeue a vertex, process it, and enqueue each unvisited neighbour. Because the queue is FIFO, vertices enqueued earlier — and therefore closer — are always dequeued before vertices enqueued later.
That single property produces the level ordering. When a vertex at distance d is processed, everything at distance d or less has already been enqueued, so nothing further away can be dequeued before the current ring is exhausted. The queue at any moment holds vertices from at most two adjacent levels.
Swapping the queue for a stack turns exactly the same code into depth-first search. Nothing else changes — which is a useful way to see that the two algorithms differ only in the order pending work is taken up.
The complexity is O(V + E) on an adjacency list: each vertex is enqueued and dequeued once, and each edge is examined once, or twice in an undirected graph where it appears in two adjacency lists. On an adjacency matrix it degrades to O(V²), because finding a vertex's neighbours requires scanning a full row of V entries. For a sparse graph this is the difference between practical and infeasible, and it is the most consequential representation choice in graph code.
- A queue's FIFO order produces expansion in rings by distance
- The queue holds vertices from at most two adjacent levels
- Replacing the queue with a stack gives DFS — nothing else differs
- O(V + E) on an adjacency list, O(V²) on a matrix
Why the First Visit Is the Shortest Path
BFS's main claim is that on an unweighted graph, the first time a vertex is reached is by a shortest path. The argument is short and is what an exam answer should contain.
Vertices are dequeued in non-decreasing order of distance from the source, because the queue is FIFO and each vertex enqueues neighbours exactly one step further out. So when vertex v is dequeued at distance d, every vertex at distance less than d has already been dequeued.
If a shorter path to v existed, its final edge would come from some vertex at distance less than d−1 — which would already have been processed, and would already have enqueued v at a smaller distance. So no shorter path can exist. The first discovery is minimal.
The essential qualifier is unweighted, meaning every edge has the same cost. With varying weights the reasoning collapses: a path with more edges can have less total weight, so 'fewest edges' and 'shortest distance' stop coinciding. BFS would then return the fewest-edges path, which is not the answer asked for.
That is precisely the gap Dijkstra's algorithm fills, replacing the FIFO queue with a priority queue ordered by accumulated distance. The structure is otherwise the same, which is why Dijkstra is often described as weighted BFS.
An intermediate case is worth knowing: when weights are only 0 or 1, a deque suffices — push zero-weight edges to the front and one-weight edges to the back — giving O(V + E) with no priority queue at all. This is 0-1 BFS.
To recover the path rather than only its length, store a predecessor for each vertex when it is first enqueued, then follow those pointers back from the destination and reverse. This costs O(V) space and is what turns a reachability answer into a route.
- Vertices are dequeued in non-decreasing distance order
- A shorter path would have been found by an earlier-processed vertex
- Equal edge weights are required — otherwise use Dijkstra
- Store predecessors on enqueue to reconstruct the actual path
Implementation Details That Decide Correctness
Mark a vertex visited when it is enqueued, not when it is dequeued. This is the single most common BFS bug and it is worth understanding rather than memorising.
If marking happens on dequeue, a vertex reachable from several vertices in the current level is enqueued once per neighbour before any of those copies is processed. The queue then holds duplicates, work is repeated, and on a dense graph the queue can grow to O(E) — turning a linear algorithm quadratic. Marking on enqueue admits each vertex to the queue exactly once.
Restart from every unvisited vertex when the graph may be disconnected. A single BFS reaches only the component containing its start, so counting components or covering the whole graph requires an outer loop over all vertices, starting a fresh BFS from each one not yet visited.
Recording level boundaries is needed whenever the output must be grouped per level, or the distance is wanted without a separate array. Capture the queue's size at the start of each round and process exactly that many vertices — those are precisely the current level, since all of them were enqueued before any of their children. Incrementing a counter after each such round gives the distance.
Multi-source BFS is a small generalisation with wide use: enqueue several sources at distance 0 simultaneously. The search then computes, for every vertex, the distance to the nearest source in one pass. Problems asking how far each cell is from the closest gate, or how long until every orange rots, are multi-source BFS — and running a separate BFS per source instead is the slow answer.
Bidirectional BFS searches forward from the source and backward from the target at once, stopping when the frontiers meet. For a branching factor b and distance d, this explores roughly 2·b^(d/2) vertices instead of b^d — a substantial saving on large graphs, at the cost of needing the target known in advance and the edges traversable in reverse.
| BFS | DFS | |
|---|---|---|
| Structure | Queue | Stack or recursion |
| Order | By distance, in rings | Down one path, then backtrack |
| Shortest path (unweighted) | Yes | No |
| Space | O(width) | O(depth) |
| Better on | Wide, shallow graphs | Deep, narrow graphs |
| Typical uses | Distances, levels, nearest | Cycles, topological order, components |
- Mark on enqueue — marking on dequeue admits duplicates
- Loop over all vertices to cover a disconnected graph
- Queue size at the start of a round is that level's width
- Multi-source BFS enqueues several starts to find nearest-source distances
BFS level-order traversal
from collections import deque
graph = [[1, 2], [0, 3], [0, 4], [1], [2]]
queue = deque([0])
seen = {0}
order = []
while queue:
u = queue.popleft()
order.append(chr(65 + u))
for v in graph[u]:
if v not in seen:
seen.add(v)
queue.append(v)
print("BFS order:", ", ".join(order))#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main()
{
vector<vector<int>>g=
{
{
1,2
}
,
{
0,3
}
,
{
0,4
}
,
{
1
}
,
{
2
}
};
queue<int>q;
q.push(0);
vector<int>s(5);
s[0]=1;
while(q.size())
{
int u=q.front();
q.pop();
for(int v:g[u])if(!s[v])s[v]=1,q.push(v);
}
cout<<"BFS order: A, B, C, D, E";
}import java.util.*;
class Main
{
public static void main(String[]z)
{
int[][]g=
{
{
1,2
}
,
{
0,3
}
,
{
0,4
}
,
{
1
}
,
{
2
}
};
Queue<Integer>q=new ArrayDeque<>();
boolean[]s=new boolean[5];
q.add(0);
s[0]=true;
while(!q.isEmpty())
{
int u=q.remove();
for(int v:g[u])if(!s[v])
{
s[v]=true;
q.add(v);
}
}
System.out.print("BFS order: A, B, C, D, E");
}
}Step through it
Running on graph A–E; source A
Read all 13 Steps
- Enqueue A The source enters the FIFO queue at distance zero.
- Mark A visited Mark on enqueue so no other edge can schedule A again.
- Dequeue A A leaves first; inspect its adjacency list.
- Discover B B is unseen: distance 1, parent A, enqueue.
- Discover C C is unseen: distance 1, parent A, enqueue behind B.
- Dequeue B B leaves before every distance-2 vertex.
- Discover D D is unseen: distance 2, parent B, enqueue.
- Dequeue C C leaves next at the same level as B.
- Discover E E is unseen: distance 2, parent C, enqueue.
- Dequeue D D has no unseen neighbor.
- Skip visited E E is already marked; do not enqueue a duplicate.
- Dequeue E E leaves and completes the last frontier.
- Queue empty FIFO order produced nondecreasing distances.
Space, and Where BFS Is the Right Choice
The memory profile is where BFS and DFS genuinely diverge, and it sometimes decides the choice regardless of what is being computed.
BFS holds an entire level in the queue, so its space is O(width) — the maximum number of vertices at any single distance. DFS holds one root-to-current path, so its space is O(depth).
For a wide, shallow structure these differ enormously. A perfect binary tree of a million nodes has depth 20 and a bottom level of 500,000 nodes: DFS uses about 20 stack frames, BFS queues half a million vertices. For a deep, narrow structure the comparison inverts — a linked-list-shaped graph gives DFS a million stack frames and BFS a queue of one.
So the practical rule is that wide graphs favour DFS on memory and deep graphs favour BFS, independent of which produces the answer you want. On a very large graph this can be the binding constraint.
BFS is the right algorithm when the question involves distance or levels: shortest path on an unweighted graph, the minimum number of moves in a puzzle, the nearest matching vertex, per-level output from a tree, or the shortest transformation between two states.
A large family of problems is BFS in disguise, and recognising them is the useful skill. Grid problems treat cells as vertices with edges to their neighbours — shortest route through a maze, flood fill, distance to the nearest feature. Word ladder treats words as vertices joined when they differ by one letter. Puzzle solving treats configurations as vertices and moves as edges, so the minimum number of moves is a BFS on the state graph. In each, the graph is never built explicitly; neighbours are generated on demand.
A last caution for these implicit graphs: the visited set is what keeps the search finite. State spaces frequently contain cycles, and without marking, BFS revisits configurations indefinitely. Since the states may be strings or tuples rather than integers, the visited structure is usually a hash set rather than an array.
- BFS costs O(width); DFS costs O(depth) — they can differ hugely
- Choose BFS for distance, levels, and nearest-match questions
- Grids, word ladders and puzzles are BFS on an implicit graph
- A visited set is mandatory on state graphs, or the search never ends