目录前言核心思想容器队列code常见的坑点前言最近在刷 LeetCode 连带着把基础算法梳理了一遍。以前写业务代码总觉得算法离自己很远但真到了做 3D 深层的时候发现根本绕不开。在用 Three.js 处理复杂的 场景图 遍历或者写 WebGL 相关的八叉树空间算法时底层的树和图遍历逻辑直接决定了渲染性能。核心思想BFS 的核心逻辑层层推进。可想象为往池塘里扔了一块石头水波是一圈一圈往外扩散的。BFS 也是这样从起点开始先把距离为 1 的周围节点全摸一遍然后再去摸距离为 2 的这种特性决定了 BFS 适合用来解决两类问题层序遍历比如把树的节点一层层打印出来无权图的最短路径比如迷宫寻路、社交网络找几度人脉容器队列在js里实现 BFS最核心的数据结构就是队列。口诀先进先出。在 JS 数组里也就是靠 push() 进队靠 shift() 出队。codefunction bfs(root) { if (!root) return; // 1. 初始化队列把起点塞进去 const queue [root]; // (可选) 如果是图结构需要记录访问过的节点防死循环 // const visited new Set(); // visited.add(root); let step 0; // 记录扩散的层数/步数 // 2. 只要队列不为空就一直榨干它 while (queue.length 0) { // 关键点要先缓存当前层的节点数量 // 因为在遍历这一层的时候还会往队列里塞下一层的节点 const size queue.length; // 3. 一次性把当前层的所有节点全部处理完 for (let i 0; i size; i) { // 拿出队头节点 const current queue.shift(); // --- 在这里做具体的业务逻辑处理 --- // console.log(current.val); // 4. 把当前节点的相邻节点下一层塞进队列 if (current.left) queue.push(current.left); if (current.right) queue.push(current.right); // 如果是图结构找邻居大概长这样 // for (const neighbor of current.neighbors) { // if (!visited.has(neighbor)) { // queue.push(neighbor); // visited.add(neighbor); // } // } } // 当前层处理完毕步数 1 step; } } 常见的坑点忘了按层处理直接 queue.shift() 然后就去判断邻居了没加那个 for 循环。如果只是想遍历所有节点那没问题。但如果要求最短路径长度或者按层输出那个 for (let i 0; i size; i) 是不能省的它保证了每一轮 while 循环处理的都是同一圈的人。图遍历忘了去重如果是树比如 DOM 树结构它是单向的不需要去重。但如果是图节点之间互相指必须要用 Set 记录 visited。节点在加入队列时就要标记为已访问而不是出队时才标记否则同一个节点可能会被上一层的多个节点重复塞进队列内存瞬间爆炸。