BFS Pathfinding
Visualizes Breadth-First Search pathfinding on a grid with obstacles.
Visualizes Depth-First Search pathfinding on a grid with obstacles.
This visualization demonstrates Depth-First Search (DFS) pathfinding on a 2D grid with obstacles. DFS is one of the two fundamental graph traversal strategies, formalized alongside BFS in the early days of graph theory. While it does not guarantee shortest paths, DFS is essential for many graph problems including cycle detection, topological sorting, and connectivity analysis.
DFS explores as far as possible along each branch before backtracking, using a LIFO stack (or recursion). When it visits a cell, it immediately pushes all unvisited neighbors onto the stack and dives into the first one. This creates a deep, winding exploration pattern that may travel far from the start before considering closer alternatives. DFS commits to a direction early, following a single path until it hits a dead end or the goal, then backtracks to try alternative routes.
The exploration pattern is visually distinctive: instead of a uniform wavefront, you see a single tendril snaking through the grid, occasionally backtracking and branching. This deep-first strategy means DFS may find a path quickly if it happens to choose the right direction, but the path it finds is often far from optimal.
| Metric | Value |
|---|---|
| Time | O(V + E) |
| Space | O(V) |
| Shortest path? | No |
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. While the worst-case space is O(V), in practice DFS often uses less memory than BFS because it only stores the current path on the stack rather than an entire frontier layer.
DFS is useful when you need any path (not necessarily the shortest), for exploring connectivity, for cycle detection, or for topological ordering of graphs. It is also the foundation of many backtracking algorithms used in constraint satisfaction problems. DFS is preferred over BFS when memory is a concern, when you want to explore deep branches first, or when all paths are equally acceptable. It is commonly used in maze generation, puzzle solving, and as a building block in algorithms like Tarjan's strongly connected components and Kosaraju's algorithm.