Overview
Breadth-First Search (BFS) explores a graph or grid layer by layer, visiting every cell at the current distance before moving one step farther. Because it fans out in expanding rings from the start, the first time it reaches the goal it has found a shortest path in any unweighted graph.
BFS uses a simple FIFO queue and treats every move as costing exactly one, which makes it the natural choice for shortest-path problems on uniform grids.
How Breadth-First Search works
- Put the start node in a FIFO queue and mark it visited.
- Dequeue the front node and look at all of its unvisited neighbours.
- Mark each neighbour visited, record the node it came from, and enqueue it.
- Repeat until the goal is dequeued, then follow the parent links back to rebuild the path.
When to use it
- Shortest path on unweighted grids and mazes, where every step has equal cost.
- Finding all nodes within a fixed number of moves, such as reachable tiles in a game.
- Prefer Dijkstra or A* once edges carry different weights.
Complexity analysis
BFS visits every vertex once and scans every edge once, giving O(V + E) time. It stores the queue and visited set, so space is O(V) — which on a wide grid can grow large. On unweighted graphs it is guaranteed to find a shortest path.
Frequently asked questions
Does BFS always find the shortest path?
On unweighted graphs, yes — because it explores in order of increasing distance, the first time it reaches the goal is via a shortest path. On weighted graphs it may not, so use Dijkstra instead.
How does BFS differ from DFS?
BFS uses a queue and expands the nearest nodes first, guaranteeing shortest paths; DFS uses a stack and plunges deep before backtracking, so it does not.