跳到主要内容

图✅

图的遍历​

答案

图的遍历主要有两种方式:深度优先搜索(DFS)和广度优先搜索(BFS)。

深度优先搜索(DFS)

function dfs (graph, start) {
const visited = new Set()
function traverse (node) {
if (visited.has(node)) return
visited.add(node)
console.log(node)
for (const neighbor of graph[node]) {
traverse(neighbor)
}
}
traverse(start)
}

const graph = {
A: ['B', 'C'],
B: ['D', 'E'],
C: ['F'],
D: [],
E: ['F'],
F: []
}

dfs(graph, 'A') // A B D E F C

广度优先搜索(BFS)

function bfs (graph, start) {
const visited = new Set()
const queue = [start]

while (queue.length > 0) {
const node = queue.shift()
if (visited.has(node)) continue
visited.add(node)
console.log(node)
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
queue.push(neighbor)
}
}
}
}

bfs(graph, 'A') // A B C D E F

最短路径算法​

给定一个加权有向图,找到从起点到终点的最短路径。

const graph = {
A: { B: 1, C: 4 },
B: { C: 2, D: 5 },
C: { D: 1 },
D: {}
}

function dijkstra (graph, start) {

}
答案
function dijkstra (graph, start) {
  const distances = {}
  const visited = new Set()
  const pq = new PriorityQueue((a, b) => a[1] < b[1])

  for (const node in graph) {
    distances[node] = Infinity
  }
  distances[start] = 0
  pq.enqueue([start, 0])

  while (!pq.isEmpty()) {
    const [current, currentDist] = pq.dequeue()
    if (visited.has(current)) continue
    visited.add(current)

    for (const neighbor in graph[current]) {
      const newDist = currentDist + graph[current][neighbor]
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist
        pq.enqueue([neighbor, newDist])
      }
    }
  }

  return distances
}

class PriorityQueue {
  constructor (comparator = (a, b) => a > b) {
    this._heap = []
    this._comparator = comparator
  }

  size () {
    return this._heap.length
  }

  isEmpty () {
    return this.size() === 0
  }

  peek () {
    return this._heap[0]
  }

  enqueue (value) {
    this._heap.push(value)
    this._siftUp()
  }

  dequeue () {
    const poppedValue = this.peek()
    const bottom = this.size() - 1
    if (bottom > 0) {
      this._swap(0, bottom)
    }
    this._heap.pop()
    this._siftDown()
    return poppedValue
  }

  _siftUp () {
    let nodeIdx = this.size() - 1
    while (nodeIdx > 0 && this._comparator(this._heap[nodeIdx], this._heap[this._parent(nodeIdx)])) {
      this._swap(nodeIdx, this._parent(nodeIdx))
      nodeIdx = this._parent(nodeIdx)
    }
  }

  _siftDown () {
    let nodeIdx = 0
    while (
      (this._left(nodeIdx) < this.size() && this._comparator(this._heap[this._left(nodeIdx)], this._heap[nodeIdx])) ||
      (this._right(nodeIdx) < this.size() && this._comparator(this._heap[this._right(nodeIdx)], this._heap[nodeIdx]))
    ) {
      const greaterChildIdx =
        this._right(nodeIdx) < this.size() && this._comparator(this._heap[this._right(nodeIdx)], this._heap[this._left(nodeIdx)])
          ? this._right(nodeIdx)
          : this._left(nodeIdx)
      this._swap(nodeIdx, greaterChildIdx)
      nodeIdx = greaterChildIdx
    }
  }

  _parent (idx) {
    return ((idx + 1) >>> 1) - 1
  }

  _left (idx) {
    return (idx << 1) + 1
  }

  _right (idx) {
    return (idx + 1) << 1
  }

  _swap (i, j) {
    [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]]
  }
}

module.exports = dijkstra

Open browser consoleTests

最小生成树​

给定一个加权无向图,找到其最小生成树。

const graph = {
A: { B: 1, C: 4 },
B: { A: 1, C: 2, D: 5 },
C: { A: 4, B: 2, D: 1 },
D: { B: 5, C: 1 }
}

function kruskal (graph) {

}
答案
function kruskal (graph) {
  const edges = []
  for (const node in graph) {
    for (const neighbor in graph[node]) {
      edges.push([node, neighbor, graph[node][neighbor]])
    }
  }
  edges.sort((a, b) => a[2] - b[2])

  const parent = {}
  const rank = {}
  for (const node in graph) {
    parent[node] = node
    rank[node] = 0
  }

  function find (node) {
    if (parent[node] !== node) {
      parent[node] = find(parent[node])
    }
    return parent[node]
  }

  function union (node1, node2) {
    const root1 = find(node1)
    const root2 = find(node2)
    if (root1 !== root2) {
      if (rank[root1] > rank[root2]) {
        parent[root2] = root1
      } else if (rank[root1] < rank[root2]) {
        parent[root1] = root2
      } else {
        parent[root2] = root1
        rank[root1]++
      }
    }
  }

  const mst = []
  for (const [node1, node2, weight] of edges) {
    if (find(node1) !== find(node2)) {
      union(node1, node2)
      mst.push([node1, node2, weight])
    }
  }

  return mst
}

module.exports = kruskal

Open browser consoleTests

拓扑排序​

给定一个有向无环图,找到其拓扑排序。

const graph = {
A: ['B', 'C'],
B: ['D'],
C: ['D'],
D: []
}

function topologicalSort (graph) {

}
答案
function topologicalSort (graph) {
  const visited = new Set()
  const stack = []
  function dfs (node) {
    if (visited.has(node)) return
    visited.add(node)
    for (const neighbor of graph[node]) {
      dfs(neighbor)
    }
    stack.push(node)
  }
  for (const node in graph) {
    dfs(node)
  }
  return stack.reverse()
}

module.exports = topologicalSort

Open browser consoleTests

网格多源扩散传播问题(Infection Spread)如何从多源 BFS 逐步演进到带状态自愈与阈值同步更新?​

给定一个二维网格,0 代表健康易感个体,1 代表感染者。
每天每个感染者可同时向上下左右 4 邻域扩散感染相邻的健康个体。
请分析从经典多源 BFS 出发,如何逐步应对免疫障碍物、自愈时间戳窗口、邻居阈值协同激活与全局消杀决策优化等一系列连续演进场景?
答案

核心结论

网格多源扩散传播问题(Infection Spread)是顶级 AI 机构(如 OpenAI)用于考核工程代码架构弹性与复杂状态演进的战役级题目。其本质是 LeetCode 994(腐烂的橘子)的高维扩展,核心演进脉络如下:

  1. Part 1 基础传播:多源广度优先搜索(Multi-Source BFS),将所有初始感染源一次性入队作为第 0 层,按波前逐层推进,时间与空间复杂度均为 $O(R \times C)$。
  2. Part 2 免疫阻隔:引入静态免疫墙(2=immune),本质为图的不可穿越障碍物节点。BFS 遇墙直接跳过;若遍历结束后仍存在无法被波前覆盖的健康个体,判定不可达并返回 -1。
  3. Part 3 自愈生命周期(时间戳标记):节点在感染第 $D$ 天自愈为 immune 不再扩散。关键陷阱在于 时钟与状态流转顺序(Off-by-one 陷阱):在当天传播判定前,必须先执行自愈判定(currentDay - infectedAt >= D 立即转为免疫),剥夺其当天继续感染邻居的资格。
  4. Part 4 阈值协同感染与死亡(双缓冲快照更新):健康格必须满足周围感染邻居数量 ≥ $K$ 才会被感染,伴随死亡倒计时。此时图的分层 BFS 骨架被打破,必须采用双缓冲快照(Double Buffering)同步演化机制:基于当前时钟全局快照统一计算所有格子在新时钟的瞬时状态,禁止原地(in-place)修改导致后续遍历格子产生状态竞争与时序污染。
  5. Part 5 全局行/列消杀灭火决策(优化问题):每天允许消杀整行或整列,目标为最小化最终死亡/感染规模。通过单步受影响感染源边际贡献评估与贪心剪枝策略,实现全局最优防控。

算法演化架构与状态流转拓扑


交互沙箱与测试套件验证

在下方交互式测试套件中,可直接运行与调试涵盖 Part 1 至 Part 5 的 5 个递进阶段完整工程级实现与 Jest 单元测试用例:

/**
 * OpenAI 经典高频面试题: Infection Spread (网络与网格多源扩散 5 连问)
 * 状态定义:
 * 0: Healthy (健康)
 * 1: Infected (感染)
 * 2: Immune / Wall (免疫 / 墙)
 * 3: Dead (死亡,Part 4/5 扩展)
 */

/**
 * Part 1: 基础多源传播 (LeetCode 994 经典多源 BFS)
 * 每天每个感染格同时感染 4 邻域健康格,求全感染天数,无法全感染返回 -1
 * @param {number[][]} grid
 * @returns {number}
 */
function infectionSpreadPart1(grid) {
  if (!grid || grid.length === 0 || grid[0].length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let healthyCount = 0;

  // 1. 拷贝网格以保证无副作用,同时统计健康格与初始感染源
  const state = grid.map(row => [...row]);
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (state[r][c] === 1) {
        queue.push([r, c, 0]);
      } else if (state[r][c] === 0) {
        healthyCount++;
      }
    }
  }

  if (healthyCount === 0) return 0;

  let maxDays = 0;
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let head = 0;

  while (head < queue.length) {
    const [r, c, day] = queue[head++];
    maxDays = Math.max(maxDays, day);

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && state[nr][nc] === 0) {
        state[nr][nc] = 1;
        healthyCount--;
        queue.push([nr, nc, day + 1]);
      }
    }
  }

  return healthyCount === 0 ? maxDays : -1;
}

/**
 * Part 2: 免疫墙隔离 (2 = immune)
 * 2 表示免疫障碍墙,既不被感染,也不向外传播。遇到墙直接跳过;若有健康格无法被感染返回 -1
 * @param {number[][]} grid
 * @returns {number}
 */
function infectionSpreadPart2(grid) {
  if (!grid || grid.length === 0 || grid[0].length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let healthyCount = 0;

  const state = grid.map(row => [...row]);
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (state[r][c] === 1) {
        queue.push([r, c, 0]);
      } else if (state[r][c] === 0) {
        healthyCount++;
      }
      // 2 为免疫墙,不做计数
    }
  }

  if (healthyCount === 0) return 0;

  let maxDays = 0;
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let head = 0;

  while (head < queue.length) {
    const [r, c, day] = queue[head++];
    maxDays = Math.max(maxDays, day);

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      // 遇到墙 (2) 或越界或非健康格跳过
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && state[nr][nc] === 0) {
        state[nr][nc] = 1;
        healthyCount--;
        queue.push([nr, nc, day + 1]);
      }
    }
  }

  return healthyCount === 0 ? maxDays : -1;
}

/**
 * Part 3: 自愈生命周期 (感染 D 天后变 immune 不再传播)
 * 核心边界时序:第 t 天感染的格,current_day - t >= D 当天先变 immune 再传播
 * 返回传播终止达到稳态的总天数,以及最终未被感染的健康格数量
 * @param {number[][]} grid
 * @param {number} D - 自愈周期 (天数)
 * @returns {{ days: number, remainingHealthy: number, finalGrid: number[][] }}
 */
function infectionSpreadPart3(grid, D) {
  if (!grid || grid.length === 0 || grid[0].length === 0) {
    return { days: 0, remainingHealthy: 0, finalGrid: [] };
  }
  const rows = grid.length;
  const cols = grid[0].length;
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  // 记录每个格子的当前状态与感染起始天数
  // -1 表示未感染
  const infectedAt = Array.from({ length: rows }, () => Array(cols).fill(-1));
  const state = grid.map((row, r) =>
    row.map((val, c) => {
      if (val === 1) {
        infectedAt[r][c] = 0;
      }
      return val;
    })
  );

  let currentDay = 0;
  let hasActiveInfection = true;

  while (hasActiveInfection) {
    hasActiveInfection = false;

    // 1. 先进行自愈判定 (current_day - t >= D 变为 immune 2)
    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        if (state[r][c] === 1) {
          if (currentDay - infectedAt[r][c] >= D) {
            state[r][c] = 2; // 免疫不再传播
          } else {
            hasActiveInfection = true; // 仍然是活跃感染源
          }
        }
      }
    }

    if (!hasActiveInfection) {
      break;
    }

    // 2. 活跃感染格向 4 邻域扩散 (当天新感染的格子在当前天结束时生效)
    const newlyInfected = [];
    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        if (state[r][c] === 1) {
          for (const [dr, dc] of dirs) {
            const nr = r + dr;
            const nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && state[nr][nc] === 0) {
              newlyInfected.push([nr, nc]);
            }
          }
        }
      }
    }

    // 3. 结算新感染格
    if (newlyInfected.length > 0) {
      for (const [nr, nc] of newlyInfected) {
        if (state[nr][nc] === 0) {
          state[nr][nc] = 1;
          infectedAt[nr][nc] = currentDay + 1;
        }
      }
    }

    currentDay++;
  }

  let remainingHealthy = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (state[r][c] === 0) remainingHealthy++;
    }
  }

  return { days: currentDay, remainingHealthy, finalGrid: state };
}

/**
 * Part 4: 阈值感染 (≥ K 个感染邻居才被感染) + 死亡/自愈倒计时
 * 必须使用双缓冲同步更新 (Double Buffering / Snapshot)
 * @param {number[][]} grid
 * @param {number} K - 邻居阈值
 * @param {{ recoveryDays?: number, deathDays?: number }} options
 * @returns {{ days: number, remainingHealthy: number, deadCount: number, finalGrid: number[][] }}
 */
function infectionSpreadPart4(grid, K = 2, options = {}) {
  const { recoveryDays = Infinity, deathDays = Infinity } = options;
  const rows = grid.length;
  const cols = grid[0].length;
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  let currentGrid = grid.map(row => [...row]);
  const infectedDaysCount = Array.from({ length: rows }, () => Array(cols).fill(0));

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (currentGrid[r][c] === 1) {
        infectedDaysCount[r][c] = 1;
      }
    }
  }

  let day = 0;
  const maxIterations = 1000;

  while (day < maxIterations) {
    let changed = false;
    // 双缓冲快照:所有判定基于 currentGrid,变更写入 nextGrid
    const nextGrid = currentGrid.map(row => [...row]);
    const nextDaysCount = infectedDaysCount.map(row => [...row]);

    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        const val = currentGrid[r][c];

        if (val === 1) {
          // 检查死亡或自愈
          const duration = infectedDaysCount[r][c];
          if (duration >= deathDays) {
            nextGrid[r][c] = 3; // 死亡
            changed = true;
          } else if (duration >= recoveryDays) {
            nextGrid[r][c] = 2; // 自愈免疫
            changed = true;
          } else {
            nextDaysCount[r][c] = duration + 1;
          }
        } else if (val === 0) {
          // 统计活跃感染邻居 (值为 1 的邻居)
          let infectedNeighbors = 0;
          for (const [dr, dc] of dirs) {
            const nr = r + dr;
            const nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && currentGrid[nr][nc] === 1) {
              infectedNeighbors++;
            }
          }

          if (infectedNeighbors >= K) {
            nextGrid[r][c] = 1;
            nextDaysCount[r][c] = 1;
            changed = true;
          }
        }
      }
    }

    currentGrid = nextGrid;
    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        infectedDaysCount[r][c] = nextDaysCount[r][c];
      }
    }

    if (!changed) break;
    day++;
  }

  let remainingHealthy = 0;
  let deadCount = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (currentGrid[r][c] === 0) remainingHealthy++;
      if (currentGrid[r][c] === 3) deadCount++;
    }
  }

  return { days: day, remainingHealthy, deadCount, finalGrid: currentGrid };
}

/**
 * Part 5: 隔离决策优化 (每天消杀/隔离一行或一列,最小化感染/死亡数)
 * 贪心策略:每一天评估如果阻断某一行或某一列能够切断的最大传播潜能
 * @param {number[][]} grid
 * @param {{ K?: number, deathDays?: number, maxActions?: number }} options
 * @returns {{ minCasualties: number, actionsTaken: Array<{ type: 'row'|'col', index: number }> }}
 */
function infectionSpreadPart5(grid, options = {}) {
  const rows = grid.length;
  const cols = grid[0].length;
  const maxActions = options.maxActions || Math.min(rows, cols);

  let currentGrid = grid.map(row => [...row]);
  const actionsTaken = [];

  for (let step = 0; step < maxActions; step++) {
    let bestAction = null;
    let minFutureCasualties = Infinity;

    // 候选动作 1: 隔离各行
    for (let r = 0; r < rows; r++) {
      // 若该行全为已阻断 (2),跳过
      if (currentGrid[r].every(v => v === 2)) continue;
      const trialGrid = currentGrid.map(row => [...row]);
      trialGrid[r] = Array(cols).fill(2); // 变为免疫阻断隔离带
      const sim = infectionSpreadPart4(trialGrid, options.K || 1, options);
      const totalCasualties = (rows * cols) - sim.remainingHealthy;
      if (totalCasualties < minFutureCasualties) {
        minFutureCasualties = totalCasualties;
        bestAction = { type: 'row', index: r, grid: trialGrid };
      }
    }

    // 候选动作 2: 隔离各列
    for (let c = 0; c < cols; c++) {
      let allImmune = true;
      for (let r = 0; r < rows; r++) {
        if (currentGrid[r][c] !== 2) {
          allImmune = false;
          break;
        }
      }
      if (allImmune) continue;

      const trialGrid = currentGrid.map(row => [...row]);
      for (let r = 0; r < rows; r++) {
        trialGrid[r][c] = 2;
      }
      const sim = infectionSpreadPart4(trialGrid, options.K || 1, options);
      const totalCasualties = (rows * cols) - sim.remainingHealthy;
      if (totalCasualties < minFutureCasualties) {
        minFutureCasualties = totalCasualties;
        bestAction = { type: 'col', index: c, grid: trialGrid };
      }
    }

    if (bestAction && minFutureCasualties < (rows * cols)) {
      actionsTaken.push({ type: bestAction.type, index: bestAction.index });
      currentGrid = bestAction.grid;
    } else {
      break;
    }
  }

  const finalSim = infectionSpreadPart4(currentGrid, options.K || 1, options);
  const casualties = (rows * cols) - finalSim.remainingHealthy;

  return { minCasualties: casualties, actionsTaken };
}

module.exports = {
  infectionSpreadPart1,
  infectionSpreadPart2,
  infectionSpreadPart3,
  infectionSpreadPart4,
  infectionSpreadPart5
};

Open browser consoleTests


核心分阶段实现解析

1. Part 1 基础传播:多源 BFS 起手

  • 统计健康格子总数 freshCount,将所有初态为 1 的坐标压入队列;
  • 若 freshCount === 0,直接返回 0 天;
  • 每次按当前层队列长度 size 批量出队,向 4 个方向扩散,将相邻的 0 置为 1,freshCount--,并压入队列;
  • 当队列为空后,检查 freshCount === 0:若全覆盖则返回经历的天数,否则返回 -1。

2. Part 2 增加免疫墙:障碍物阻隔与可达性死区

  • 免疫墙值为 2,在初始扫描时跳过墙体;
  • 扩散遍历过程中,若邻居格为 2 则视为阻断障碍;
  • 若存在被免疫墙完全环绕孤立的健康个体,多源 BFS 波前永远无法触达,最终 freshCount > 0 自动触发返回 -1。

3. Part 3 自愈生命周期:规避 Off-by-one 时钟陷阱

  • 数据结构:网格中存储状态与感染日元组 { state: 1, infectedAt: t };
  • 时序核心:若某格子在第 $t$ 天感染,自愈周期为 $D$。在第 $currentDay$ 天:
    • 如果先扩散再自愈:该格子在第 $t+D$ 天仍会向外扩散一次,导致其实际具备传染力的天数变为 $D+1$ 天;
    • 正确时序:在第 $currentDay$ 天启动时,必须先结算自愈:若 currentDay - infectedAt >= D,立即将状态置为 2,当日不再具备传播力。

4. Part 4 阈值协同感染与死亡:双缓冲同步更新

  • 为什么纯队列 BFS 骨架不再适用?因为协同感染要求“同时观察当前时钟下周围活跃感染源数量是否满足 $\ge K$”。如果边遍历边就地(in-place)修改网格,先被计算的格子感染后会错误地成为同一时钟周期内后续邻居的“感染源”,引发时钟脏读;
  • 解决方案:双缓冲快照(Double Buffering):
    const nextGrid = currentGrid.map(row => row.map(cell => ({ ...cell })));
    // 遍历所有坐标 (r, c),只读读取 currentGrid,只写写入 nextGrid
    // 计算完成一整天所有格子的瞬时变化后,再原子赋值 currentGrid = nextGrid

5. Part 5 消杀决策优化:全局行/列剪枝

  • 每一轮在执行传播与生命周期更新前,评估消杀每一行或每一列能立即清除的活跃感染源总数;
  • 选取边际收益最大的轴向进行整行/整列置 2(彻底阻断),使后续传播链条在最短周期内收敛。

面试官视角与下探考察点

  1. 架构扩展性(Refactorability):
    • 面试官通常会在前 15 分钟让候选人快速写完 Part 1。许多候选人会写出与状态值 1/0 强耦合的死逻辑;当面试官追问 Part 3(引入时间戳自愈)与 Part 4(引入阈值)时,原本基于数组就地修改的代码全部推倒重写,直接超时失败。
    • 具备 Staff / Senior 架构意识的候选人会从一开始就将“邻居探查”、“状态转移合法性校验”、“时钟步进”抽离为独立纯函数。
  2. 状态更新时序(Clock Semantics):
    • 针对 Part 3 的 currentDay - infectedAt >= D,面试官会重点考察边界用例(如 $D=1$ 时,第 0 天感染的个体在第 1 天是否还能扩散)。清楚指出“先自愈注销传播权,再执行波前扩散”是拿到 Strong Hire 的关键证明。
  3. 并发更新与无副作用(In-place vs Double Buffering):
    • 深入解释 Cellular Automata(元胞自动机,如康威生命游戏)与双缓冲快照的必要性,体现从单纯算法刷题到系统状态机工程建模的跨越。

延伸阅读

  • LeetCode 994. 腐烂的橘子(Rotting Oranges)
  • 康威生命游戏(Conway's Game of Life)与双缓冲渲染机制
  • 图论多源最短路算法与波前传播模型(Wavefront Propagation)