Depth-First Search (DFS) 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 stack and recursive calls

Optimal: No - does not guarantee shortest path

Complete: Yes (will find solution if one exists)

How it works: Explores as far as possible along each branch before backtracking. Uses a stack (LIFO) to maintain order.

Best for: Exploring all paths, maze solving, topological sorting, finding connected components.

Difference from BFS: Goes deep first, may find longer paths but uses less memory.

Implementation

function dfsPathfinding(grid, start, end) {
  const stack = [start];
  const visited = new Set();
  
  while (stack.length > 0) {
    const current = stack.pop(); // LIFO - Last In First Out
    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 (add to stack)
    const neighbors = getNeighbors(current);
    for (const neighbor of neighbors) {
      if (!visited.has(`${neighbor.row},${neighbor.col}`) 
          && neighbor.type !== "wall") {
        neighbor.parent = current;
        stack.push(neighbor); // Push to stack (LIFO)
      }
    }
  }
  
  return null; // No path found
}