DFS Pathfinding
Visualizes Depth-First Search pathfinding on a grid with obstacles.
Visualizes Breadth-First Search pathfinding on a grid with obstacles.
This visualization demonstrates Breadth-First Search (BFS) pathfinding on a 2D grid with obstacles. BFS is one of the most fundamental graph traversal algorithms, formalized in the early days of graph theory with roots tracing back to Leonhard Euler's work in the 18th century. It remains a cornerstone algorithm taught in every introductory computer science course and is widely used in practice for shortest-path problems on unweighted graphs.
BFS explores all cells at distance d before any cell at distance d+1, using a FIFO queue. Starting from the source cell, it adds all unvisited neighbors to the queue, then processes them in the order they were added. This level-by-level expansion creates a wavefront that radiates outward uniformly from the start. Because it explores in order of increasing distance, BFS guarantees the shortest path on unweighted grids. The algorithm naturally produces a shortest-path tree, and by tracking each cell's parent pointer, you can reconstruct the optimal route once the goal is reached.
The wavefront pattern is visually distinctive: you can see a roughly circular frontier expanding from the start node, exploring nearby cells before distant ones. This uniform expansion is what guarantees optimality — the first time BFS reaches the goal, it has found the shortest path.
| Metric | Value |
|---|---|
| Time | O(V + E) |
| Space | O(V) |
| Shortest path? | Yes |
Where V = cells and E = edges between adjacent cells. On a grid of size N x M, V = N x M and E is at most 4V for 4-directional movement. The space complexity comes from the queue, which in the worst case holds an entire frontier layer.
BFS is the standard choice for shortest paths on unweighted graphs or when you need to explore all reachable nodes at each distance level. It is used in GPS navigation systems, network packet routing, social network analysis for finding degrees of separation, and maze-solving applications. BFS is also the basis for more advanced algorithms like Dijkstra's (which generalizes BFS to weighted graphs) and A* (which adds heuristic guidance). When you need guaranteed shortest paths and the graph is unweighted, BFS is the simplest and most reliable choice.