BFS
广度优先
图核心时间 O(V+E)空间 O(V)
用队列一层一层扩张。无权图上第一次到达就是最短路。
动画
广度优先：从 A 出发，一层一层向外扩展。
1 / 13
- 当前
- 默认
讲解
最短路、层次遍历、连通块、建图建模题的第一选择。
- 01起点入队并标记 visited。
- 02出队 u，把它未访问的邻居入队。
- 03队列为空时遍历结束。
- 04需要路径则额外记录 parent。
易错点
- 入队时立刻标记，否则同一结点会重复入队。
- 有权图 BFS 不是最短路，应改 Dijkstra。
代码
function bfs(g, start) {
const seen = new Set([start]);
const q = [start];
const order = [];
while (q.length) {
const u = q.shift();
order.push(u);
for (const v of g[u] || []) {
if (seen.has(v)) continue;
seen.add(v); q.push(v);
}
}
return order;
}