广度优先搜索 (BFS)

目录

前言

核心思想

容器：队列

code

常见的坑点

前言

最近在刷 LeetCode ，连带着把基础算法梳理了一遍。
以前写业务代码总觉得算法离自己很远，但真到了做 3D 深层的时候，发现根本绕不开。在用 Three.js 处理复杂的 场景图 遍历，或者写 WebGL 相关的八叉树空间算法时，底层的树和图遍历逻辑直接决定了渲染性能。

核心思想

BFS 的核心逻辑：层层推进。

可想象为：往池塘里扔了一块石头，水波是一圈一圈往外扩散的。BFS 也是这样，从起点开始，先把距离为 1 的周围节点全摸一遍，然后再去摸距离为 2 的
这种特性决定了 BFS 适合用来解决两类问题：

1. 层序遍历（比如把树的节点一层层打印出来）
2. 无权图的最短路径（比如迷宫寻路、社交网络找几度人脉）

容器：队列

在js里实现 BFS，最核心的数据结构就是队列。

口诀：先进先出。在 JS 数组里，也就是靠 push() 进队，靠 shift() 出队。

code

function 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++; } } ```

常见的坑点

1. 忘了按层处理：直接 queue.shift() 然后就去判断邻居了，没加那个 for 循环。如果只是想遍历所有节点，那没问题。但如果要求最短路径长度或者按层输出，那个 for (let i = 0; i < size; i++) 是不能省的，它保证了每一轮 while 循环处理的都是同一圈的人。
2. 图遍历忘了去重：如果是树（比如 DOM 树结构），它是单向的，不需要去重。但如果是图（节点之间互相指），必须要用 Set 记录 visited。节点在加入队列时就要标记为已访问，而不是出队时才标记，否则同一个节点可能会被上一层的多个节点重复塞进队列，内存瞬间爆炸。