Graph Traversal

Seeing How Algorithms Explore

Breadth-first and depth-first search are two ways to traverse a graph. They sound abstract, but the difference is visual: one explores in concentric waves, the other dives deep before backtracking. This demo lets you watch both explore the same maze in real-time, revealing why they find different paths.

The Grid Graph

Both algorithms traverse the same structure: a grid where each cell connects to its neighbors (up, down, left, right). The maze is defined by which connections are blocked. This is a graph problem disguised as a spatial one.

// The graph is implicit in the grid
// Each cell (x, y) has up to 4 neighbors
const neighbors = [
  [x, y - 1], // up
  [x, y + 1], // down
  [x - 1, y], // left
  [x + 1, y]  // right
].filter(([nx, ny]) => 
  nx >= 0 && nx < GRID_SIZE &&
  ny >= 0 && ny < GRID_SIZE &&
  !isWall(x, y, nx, ny) // wall check
);

The Frontier

Both algorithms maintain a frontier of cells to explore. The key difference is what data structure holds that frontier:

• BFS uses a queue (FIFO) — cells are explored in the order they were discovered. This produces concentric wave expansion.
• DFS uses a stack (LIFO) — the most recently discovered cell is explored immediately. This produces deep diving behavior.

// BFS: queue — add to back, remove from front
const queue = [];
queue.push(start);
while (queue.length > 0) {
  const current = queue.shift(); // oldest first
  // ... explore neighbors and push to queue
}

// DFS: stack — add to top, remove from top
const stack = [];
stack.push(start);
while (stack.length > 0) {
  const current = stack.pop(); // newest first
  // ... explore neighbors and push to stack
}

Visited Tracking

Both algorithms must avoid revisiting cells. A visited set prevents infinite loops. The moment a cell enters the frontier, it's marked visited — not when it's explored. This ensures each cell is enqueued at most once.

const visited = new Set();

function explore(cell) {
  const key = `${cell.x},${cell.y}`;
  if (visited.has(key)) return;
  visited.add(key); // mark immediately
  // ... add neighbors to frontier
}

The Path Back

When the goal is found, we need to reconstruct the path. Each cell stores its parent — the cell from which it was discovered. Following parent pointers back to the start reconstructs the path.

const parent = new Map();

// When discovering neighbor:
parent.set(neighborKey, currentKey);

// When goal found:
function reconstructPath(goal) {
  const path = [goal];
  let current = goal;
  while (parent.has(key(current))) {
    current = parent.get(key(current));
    path.unshift(current);
  }
  return path;
}

Why BFS Finds the Shortest Path

BFS explores in layers — all cells at distance 1, then all cells at distance 2, then distance 3, and so on. The first time the goal is discovered, we're guaranteed to have found it via the shortest path. This is a theorem: BFS finds shortest paths in unweighted graphs.

DFS has no such guarantee. It might find a long path first because it dives deep. The path DFS finds depends on the order neighbors are enumerated.

What This Reveals

The frontier data structure is not an implementation detail — it's the entire character of the algorithm. Replace the queue with a priority queue (weighted graphs), and you get Dijkstra's algorithm or A*. The frontier is where algorithmic personality lives. BFS is patient and methodical. DFS is impulsive and thorough. Both are correct, but they move through possibility space in fundamentally different shapes.