BFS (Grid)

Graphs

avgO(V + E)worstO(V + E)spaceO(V)

Start at (7, 2): it is the only cell in the queue

1 / 376

Code

function bfs(grid: Grid, start: number, end: number) {  const prev = new Map<number, number>();  const seen = new Set([start]);  const queue = [start];  while (queue.length > 0) {    const cell = queue.shift()!;    if (cell === end) return buildPath(prev, end);    for (const next of grid.neighbours(cell)) {      if (grid.isWall(next) || seen.has(next)) continue;      seen.add(next);      prev.set(next, cell);      queue.push(next);    }  }  return []; // the queue ran dry: end is unreachable}function buildPath(prev: Map<number, number>, end: number) {  const path = [end];  while (prev.has(path[0])) path.unshift(prev.get(path[0])!);  return path;}

procedure BFS(grid, start, end)  prev ← empty map  seen ← {start}  queue ← [start]  while queue is not empty do    cell ← dequeue(queue)    if cell = end then return buildPath(prev, end)    for each neighbour next of cell (up, right, down, left) do      if next is a wall or next ∈ seen then skip it      add next to seen      prev[next] ← cell      enqueue(queue, next)    end for  end while  return no pathend procedureprocedure buildPath(prev, end)  path ← [end]  while prev[first of path] exists do prepend it to path  return pathend procedure

Variables

queue=1

Counters

visited: 0
enqueued: 0

Draw

Size

Drag on the grid to draw. Grab the start or end cell to move it. Edits re-run the search from step 1.

How it works

Breadth-first search spreads out from the start one ring at a time using a FIFO queue, so cells are reached in order of their distance in moves. The first time it dequeues the end it has found a shortest path, which it rebuilds by following each cell's prev link back to the start.

Complexity

Best: O(1)
Average: O(V + E)
Worst: O(V + E)
Space: O(V)

BFS (Grid)

How it works

Complexity

Search algorithms