Breadth-First Search
BFS explores a graph in rings: everything one step away, then everything two steps away, and so on. That expanding-frontier behaviour is not a side effect — it is a guarantee, and it is precisely why BFS finds shortest paths on unweighted graphs while depth-first search does not.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int main() {
int n = 6;
vector<vector<int> > adj(n);
adj[0].push_back(1); adj[0].push_back(2);
adj[1].push_back(3); adj[2].push_back(3);
adj[3].push_back(4); adj[4].push_back(5);
vector<int> dist(n, -1);
vector<int> q;
q.push_back(0);
dist[0] = 0;
int head = 0;
while (head < (int)q.size()) {
int u = q[head++];
for (int i = 0; i < (int)adj[u].size(); i++) {
int v = adj[u][i];
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push_back(v);
}
}
}
for (int i = 0; i < n; i++) cout << dist[i] << ' ';
return 0;
}dist doubles as the visited marker — a value of -1 means undiscovered, which removes the need for a separate boolean array.
How it works, step by step
The queue is the frontier
At any moment the queue holds nodes at distance d and d+1 from the source, in that order. Dequeuing in FIFO order means you never process a node at distance d+1 before finishing every node at distance d.
First discovery is shortest
Because the frontier expands outward one ring at a time, the first time you reach a node is via a shortest path. That is the entire correctness argument for BFS shortest paths, and it fails the moment edges have different weights.
Mark on enqueue, not on dequeue
Setting dist[v] the moment v is discovered stops it being enqueued again by another node in the same ring. Marking on dequeue instead lets a node sit in the queue several times, which is still correct but can blow the queue up to O(E) entries.
Distances come free
dist[v] = dist[u] + 1 works because u is being processed at the moment v is discovered, and u already holds its final distance. No extra pass is needed to compute the layer numbers.
Every edge is examined once per direction
The outer loop dequeues each node once and the inner loop walks its adjacency list. Summed over all nodes, that is exactly E iterations for a directed graph, giving the O(V + E) bound.
Complexity
Every vertex enters the queue once and every adjacency entry is scanned once, so the cost is proportional to the graph's size rather than its shape; the space is the queue plus the distance array, and the queue peaks at the size of the widest ring.
Common bugs
Marking visited on dequeue instead of enqueue
If the check happens when a node comes off the queue, a node with many in-edges gets enqueued once per neighbour before it is ever processed. The result is still correct but the queue can hold O(E) entries, and on a dense graph that is a memory blowup rather than a wrong answer — which makes it hard to spot in tests.
Using BFS on a weighted graph
BFS counts edges, not weights. On a graph where one edge costs 100 and a two-edge path costs 2, BFS confidently reports the wrong shortest path. If any edge weight differs from any other, you need Dijkstra — or, for 0/1 weights, a deque-based variant.
Dequeuing with erase(q.begin())
This shifts the whole vector on every pop, turning an O(V + E) traversal into O(V squared). It is functionally correct, which is why it survives code review, and it is the single most common reason a BFS solution times out.
Forgetting to mark the source
If dist[0] is left at -1, the source can be rediscovered through a cycle and re-enqueued, and on a graph with a cycle back to the start you get an infinite loop. Watching node 0 reappear in the queue is the fastest way to see it.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why does BFS find the shortest path?
Because it processes nodes strictly in order of distance from the source: every node at distance d is dequeued before any node at distance d+1. The first time a node is discovered, it must therefore be via a minimum-edge-count path. This guarantee holds only for unweighted graphs, where every edge counts the same.
What is the difference between BFS and DFS?
BFS uses a queue and explores level by level, discovering nodes in order of increasing distance from the source. DFS uses a stack (usually the call stack) and follows one path as deep as it goes before backtracking. BFS finds shortest paths on unweighted graphs; DFS is better for cycle detection, topological sorting, and connectivity questions.
What is the time complexity of BFS?
O(V + E) — every vertex is enqueued and dequeued once, and every edge is examined once from its source. The V term covers the vertices themselves and the E term covers scanning the adjacency lists. Using the wrong container for the queue, such as erasing from the front of a vector, silently degrades this to O(V squared).
Can BFS be used on a weighted graph?
Not for shortest paths, unless every edge has the same weight. BFS minimises the number of edges, which only equals minimum total weight when all weights are equal. For general non-negative weights use Dijkstra; for graphs where all weights are 0 or 1, a double-ended queue variant of BFS works.