BFS — Breadth-First Search Algorithm Explained

Breadth-first search, or BFS, is a graph algorithm that visits nodes in order of their distance from a start node. It checks every node that is one edge away before moving to nodes that are two edges away, then three edges away, and so on.

That layer-by-layer order is the key idea. If the graph is unweighted, or every edge has the same cost, BFS also gives the shortest path length from the start node to every reachable node.

What Breadth-First Search Does

BFS uses a queue, which is a first-in, first-out list. The queue is what preserves the layer order: nodes discovered earlier are processed earlier.

The usual pattern is:

• mark the start node visited
• put it into the queue
• remove the front node
• add each unvisited neighbor to the back of the queue
• repeat until the queue is empty

If you also store each node's parent, you can reconstruct one shortest path after the search finishes.

Why The Queue Creates Layers

Suppose node $A$ is the start. Its direct neighbors are distance $1$ from $A$, so they enter the queue first. Only after those nodes are processed do their unvisited neighbors enter, which means the next wave has distance $2$.

That is why BFS naturally groups nodes by distance from the start. It is not estimating which path is short. The queue forces the search to finish all paths with fewer edges before it considers longer ones.

BFS Example: Finding The Shortest Path By Edge Count

Use this graph:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

Start at $A$. The queue changes like this:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

Here is what that means:

First, process $A$, then add $B$ and $C$. Next, process $B$ and then $C$, which adds $D$ and $E$. After that, process $D$ and $E$, which reaches $F$.

So the BFS visit order is:

$$A,\ B,\ C,\ D,\ E,\ F$$

The distances from $A$ are:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

This shows the main payoff. BFS reaches $F$ at distance $3$, so the shortest path from $A$ to $F$ uses $3$ edges. One shortest path is $A \to B \to D \to F$. Another is $A \to C \to E \to F$.

Common BFS Mistakes

Assuming BFS Always Finds The Cheapest Path

That is only true when every edge has the same cost, or when the graph is treated as unweighted. If edges have different weights, BFS may find a path with fewer edges but a higher total cost.

Marking A Node Too Late

In standard BFS, a node is usually marked visited when it is enqueued, not when it is later removed. That prevents the same node from being added to the queue many times.

Mixing Up BFS And DFS

BFS explores by layers. Depth-first search, or DFS, keeps following one branch before backing up. They answer different kinds of questions well.

Forgetting That Order Can Depend On Neighbor Order

The exact visit order inside the same layer can change depending on how neighbors are listed. The distance guarantees still hold, but the traversal order may differ.

When Breadth-First Search Is Used

BFS is useful when you care about reachability, level-order traversal in trees, or shortest path lengths measured by number of edges.

It also appears in state-space problems where each move has the same cost. Under that condition, BFS is often the clearest way to find the minimum number of moves.

A Simple Way To Remember BFS

Think of BFS as a ripple spreading outward from the start node. Every ripple step adds one more edge of distance.

To try your own version, draw a small graph, pick a start node, and write the queue after each step. If you want a next step, solve a similar graph-traversal problem and check whether the shortest path claim still holds when the graph is weighted.