BFS算法路径可视化工具起止节点距离过远时运行失效问题求助

问题核心原因 #

• 最致命的逻辑错误：边界准入判断的逻辑运算符使用错误，||（或）应改为&&（且）。你现有代码中else if(u.className!="start" || u.className!="visited")的判断结果恒为真：任意节点只要不是起点、或者不是已访问节点，都会被判定为符合条件，已经标记为visited的节点会被反复加入队列，队列规模指数级膨胀，直接导致计算卡顿甚至程序卡死。
• 频繁DOM操作开销过高：每次遍历都调用getElementById查询节点、拆分id字符串获取坐标，DOM操作的执行效率远低于纯内存运算，当BFS遍历节点量上升后，耗时会陡增。
• 队列实现效率低下：如果你的自定义Queue是基于普通数组的shift()方法实现出队，shift()的时间复杂度为O(n)，队列长度越大，出队操作耗时越高。

优化方案 #

1. 修复逻辑判断 #

将四个方向判断中的||全部替换为&&，如果你的工具支持设置障碍物，可同时补充障碍物节点的排除逻辑：

// 修改前
else if(u.className!="start" || u.className!="visited")
// 修改后（block对应你的障碍物类名，没有可删除该条件）
else if(u.className!="start" && u.className!="visited" && u.className!="block")

2. 减少不必要的DOM操作 #

初始化阶段提前将网格所有节点预存到二维数组，同时给节点挂载data-row、data-col自定义属性，不需要每次遍历都拆分id获取坐标：

// 工具初始化时执行一次即可，预存所有网格节点
const grid = new Array(21).fill(0).map(() => new Array(51))
document.querySelectorAll('td').forEach(node => {
  const [row, col] = node.id.split('-').map(Number)
  grid[row][col] = node
  node.dataset.row = row
  node.dataset.col = col
})

遍历节点时直接从预存数组取节点，坐标直接从节点自定义属性读取：

const row = Number(x.dataset.row)
const col = Number(x.dataset.col)
// 向上遍历时直接从数组取对应节点，无需调用getElementById
const u = grid[row-1][col]

3. 优化队列实现 #

改用时间复杂度为O(1)的高效队列实现，避免使用数组shift()方法：

class Queue {
  constructor() {
    this.inStack = []
    this.outStack = []
  }
  // 入队
  enqueue(item) {
    this.inStack.push(item)
  }
  // 出队
  dequeue() {
    if (this.outStack.length === 0) {
      while (this.inStack.length) {
        this.outStack.push(this.inStack.pop())
      }
    }
    return this.outStack.pop()
  }
  // 判断队列是否为空
  isEmpty() {
    return this.inStack.length === 0 && this.outStack.length === 0
  }
}

4. 补充路径回溯逻辑（可选） #

现有代码仅实现了遍历逻辑，没有记录节点的父节点，无法生成最终的最短路径。你可以在遍历时为每个节点挂载父节点属性，找到终点后从终点反向回溯到起点即可得到最短路径。

内容的提问来源于stack exchange，提问作者user15409086