Breadth-First Search (BFS) Pathfinding

Speed:

SlowFast

Start

End

Wall

Visited

Current

Path

Operation Logs

No operations yet

Algorithm Info

Time Complexity: O(V + E) where V = vertices, E = edges

Space Complexity: O(V) for the queue and visited set

Optimal: Yes for unweighted graphs (finds shortest path)

Complete: Yes (will find solution if one exists)

How it works: Explores all nodes at distance k before exploring nodes at distance k+1. Uses a queue (FIFO) to maintain order.

Best for: Unweighted graphs, finding shortest path in terms of number of edges.

Implementation

function bfsPathfinding(grid, start, end) {
  const queue = [start];
  const visited = new Set();
  start.distance = 0;
  
  while (queue.length > 0) {
    const current = queue.shift();
    const key = `${current.row},${current.col}`;
    
    if (visited.has(key)) continue;
    visited.add(key);
    
    // Found the end!
    if (current === end) {
      return reconstructPath(end);
    }
    
    // Explore neighbors
    const neighbors = getNeighbors(current);
    for (const neighbor of neighbors) {
      if (!visited.has(`${neighbor.row},${neighbor.col}`) 
          && neighbor.type !== "wall") {
        neighbor.distance = current.distance + 1;
        neighbor.parent = current;
        queue.push(neighbor);
      }
    }
  }
  
  return null; // No path found
}