DFS (Grid)

Graphs

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

Start at (7, 2): it is the only cell on the stack

1 / 270

Code

function dfs(grid: Grid, start: number, end: number) {  const prev = new Map<number, number>();  const seen = new Set<number>();  const stack = [start];  while (stack.length > 0) {    const cell = stack.pop()!;    if (seen.has(cell)) continue; // a stale copy: already explored    seen.add(cell);    if (cell === end) return buildPath(prev, end);    // Push in reverse so the first neighbour (up) is popped first.    for (const next of grid.neighbours(cell).reverse()) {      if (grid.isWall(next) || seen.has(next)) continue;      prev.set(next, cell);      stack.push(next);    }  }  return []; // the stack 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 DFS(grid, start, end)  prev ← empty map  seen ← ∅  stack ← [start]  while stack is not empty do    cell ← pop(stack)    if cell ∈ seen then skip it    add cell to seen    if cell = end then return buildPath(prev, end)    ▷ reversed, so "up" ends on top of the stack    for each neighbour next of cell (left, down, right, up) do      if next is a wall or next ∈ seen then skip it      prev[next] ← cell      push(stack, 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

stack=1

Counters

visited: 0
pushed: 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

Depth-first search keeps going in one direction (up first, then right, down and left) and only backtracks to the most recent unexplored cell on its stack when it hits a dead end. It always finds a path if one exists, but usually a long, winding one rather than the shortest.

Complexity

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

DFS (Grid)

How it works

Complexity

Search algorithms