Pathfinding Algorithm
Breadth-First Search
“The Cautious Explorer”
History
Breadth-First Search (BFS) has roots in the 1940s with Konrad Zuse, but it was formally published by Edward F. Moore in 1959 at Bell Labs. Moore was trying to find the shortest path out of a maze, proving that sometimes the best way to exit a labyrinth is to try every single direction simultaneously.
It is the "vanilla" ice cream of graph theory. Reliable, foundational, and widely liked, even if it lacks the exotic toppings of newer heuristics. Its behavior mirrors a ripple spreading across a pond or a rumor spreading through a slack channel.
How It Works
BFS is the definition of "slow and steady wins the race." It explores the graph layer by layer, visiting every neighbor at the current distance before moving one step further out.
The Algorithm Step-by-Step
- Initialize: Add the start node to a queue and mark it as visited.
- Dequeue: Remove the node at the front of the line.
- Check Goal: If this is the destination, you're done.
- Expand: For every unvisited neighbor, mark it as visited, record its parent (so we can trace the path back later), and add it to the back of the queue.
- Repeat: Keep going until the queue is empty or the goal is found.
Why It Guarantees Shortest Path
Because BFS explores radially. You cannot physically reach a node at distance 5 before finishing all nodes at distance 4. Therefore, the moment you touch the goal, you have found the shortest route in an unweighted graph.
The Queue's Role
The Queue (FIFO) ensures fair processing. It prevents the algorithm from getting distracted and diving down a rabbit hole.
We visit every Vertex once and check every Edge once. In a grid, this is proportional to the area searched. It's efficient, but it doesn't skip any work.
The 'frontier' (the rim of the ripple) grows as the search expands. In a worst-case open grid, this can get memory-heavy quickly.
The core data structure powering Breadth-First Search.
How this algorithm appears during visualization.
Code Walkthrough
Real implementations in multiple programming languages. Select a language to view idiomatic code.
1from collections import deque23def bfs(grid: list[list[int]], start: tuple[int, int], end: tuple[int, int]) -> list[tuple[int, int]] | None:4 """Find shortest path in grid using BFS. 0 = passable, 1 = wall."""5 rows, cols = len(grid), len(grid[0])6 queue = deque([(start, [start])])7 visited = {start}8 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]910 while queue:11 (row, col), path = queue.popleft()1213 if (row, col) == end:14 return path1516 for dr, dc in directions:17 new_row, new_col = row + dr, col + dc1819 if (0 <= new_row < rows and 0 <= new_col < cols20 and grid[new_row][new_col] == 021 and (new_row, new_col) not in visited):22 visited.add((new_row, new_col))23 queue.append(((new_row, new_col), path + [(new_row, new_col)]))2425 return NoneReal World Use Cases
- 1GPS Navigation (in unweighted grids)
- 2Social Networks (finding 'degrees of separation')
- 3Web Crawlers (limiting search depth)
- 4Broadcasting in peer-to-peer networks
- 5Garbage Collection (identifying live objects)
- 6Solving Rubik's Cubes (minimum move solutions)
Key Insights
- It is the gold standard for unweighted graphs.
- It explores equally in all directions, which is safe but can be slow.
- It requires more memory than DFS because it stores the entire frontier.
- It forms the basis for more complex algorithms like Dijkstra and A*.
- It will always find a solution if one exists.
When to Use
Use BFS when you need the shortest path in a graph where all edges have the same cost (or no cost). It is perfect for procedural generation and proximity checks.
When NOT to Use
Avoid BFS if the graph is weighted (it ignores costs) or if the target is likely to be very far away, as the memory usage can explode.