Graph BFS and DFS

// Turn an edge list into an adjacency list once, up front: adj[u] is the array of u's neighbours, so
// looping over a node's neighbours costs O(its degree) instead of a scan over every edge.
export function buildAdjacency(n, edges, directed = false) {
  const adj = Array.from({ length: n }, () => []); // n separate arrays (not fill([]), which shares one)
  for (const [a, b] of edges) {
    adj[a].push(b);
    if (!directed) adj[b].push(a);                 // an undirected edge is stored in both directions
  }
  return adj;
}

// When nodes are strings or sparse numbers ("JFK", 10^9), key a Map by node instead of using an array.
export function buildAdjacencyMap(edges, directed = false) {
  const adj = new Map();
  const add = (from, to) => {
    if (!adj.has(from)) adj.set(from, []);
    if (to !== undefined) adj.get(from).push(to);
  };
  for (const [a, b] of edges) {
    add(a, b);
    if (directed) add(b);                          // make sure sinks exist as keys too
    else add(b, a);
  }
  return adj;
}

// Template 1a: recursive DFS on a grid. A grid is an implicit graph: cell (r, c) is a node and its
// neighbours are the in-bounds cells one step away. Counts the regions of connected cells equal to `target`.
export function countRegions(grid, target = 1) {
  const rows = grid.length;
  const cols = rows > 0 ? grid[0].length : 0;
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  function dfs(r, c) {
    seen[r][c] = true;                                          // mark before exploring further
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // off the grid
      if (seen[nr][nc] || grid[nr][nc] !== target) continue;      // visited, or not part of a region
      dfs(nr, nc);
    }
  }

  let regions = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === target && !seen[r][c]) {
        regions++;                                              // nothing earlier reached it: a new region
        dfs(r, c);
      }
    }
  }
  return regions;
}

// Template 1b: the same flood with an explicit stack, so a huge region can't overflow the call stack.
// Returns the size of every region in the order the scan finds them.
export function regionSizes(grid, target = 1) {
  const rows = grid.length;
  const cols = rows > 0 ? grid[0].length : 0;
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  const sizes = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== target || seen[r][c]) continue;
      seen[r][c] = true;                                        // mark on push
      const stack = [[r, c]];
      let size = 0;
      while (stack.length > 0) {
        const [cr, cc] = stack.pop();
        size++;
        for (const [dr, dc] of dirs) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
          if (seen[nr][nc] || grid[nr][nc] !== target) continue;
          seen[nr][nc] = true;
          stack.push([nr, nc]);
        }
      }
      sizes.push(size);
    }
  }
  return sizes;
}

// Template 2: BFS from one start node. Nodes come out of the queue in order of distance, so the first time a
// node is discovered is along a fewest-edges path. dist[v] = number of edges from start, or -1 if unreachable.
export function bfsDistances(adj, start) {
  const dist = new Array(adj.length).fill(-1);  // -1 doubles as "not visited"
  dist[start] = 0;                              // mark the start when it is enqueued
  const queue = [start];
  for (let head = 0; head < queue.length; head++) { // head index: queue.shift() would be O(n) per call
    const node = queue[head];
    for (const next of adj[node]) {
      if (dist[next] !== -1) continue;          // already queued, so its distance is final
      dist[next] = dist[node] + 1;              // mark on enqueue
      queue.push(next);
    }
  }
  return dist;
}

// Fewest moves between two cells of a grid of strings ("." open, "#" wall), one level per step. -1 if blocked.
export function gridSteps(grid, [sr, sc], [tr, tc]) {
  const rows = grid.length;
  const cols = grid[0].length;
  if (grid[sr][sc] === "#" || grid[tr][tc] === "#") return -1;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  seen[sr][sc] = true;
  const queue = [[sr, sc]];
  let head = 0;
  for (let steps = 0; head < queue.length; steps++) {
    const levelEnd = queue.length;              // everything queued so far is `steps` moves away
    while (head < levelEnd) {
      const [r, c] = queue[head++];
      if (r === tr && c === tc) return steps;
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (seen[nr][nc] || grid[nr][nc] === "#") continue;
        seen[nr][nc] = true;
        queue.push([nr, nc]);
      }
    }
  }
  return -1;
}

// Template 3: multi-source BFS. Every source starts in the queue at distance 0, so one pass gives each cell its
// distance to the NEAREST source. Grid of strings: "E" exit (a source), "." open, "#" wall; -1 = unreachable.
export function distanceToNearest(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
  const queue = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "E") {
        dist[r][c] = 0;                           // all sources are seeded (and marked) together
        queue.push([r, c]);
      }
    }
  }
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (let head = 0; head < queue.length; head++) {
    const [r, c] = queue[head];
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (grid[nr][nc] !== "." || dist[nr][nc] !== -1) continue;
      dist[nr][nc] = dist[r][c] + 1;              // first discovery = nearest source
      queue.push([nr, nc]);
    }
  }
  return dist;
}