Graph Breadth-First Search
BFS explores a graph level by level using a queue. In an unweighted graph it finds shortest paths by number of edges.
先从这个心智模型开始
BFS explores a graph level by level using a queue. In an unweighted graph it finds shortest paths by number of edges.
它如何工作，不堆砌不必要的术语
Enqueue the start and mark it visited.
Repeatedly dequeue one node and enqueue unseen neighbors.
把算法读成一连串决策
Define directed/undirected and weighted/unweighted assumptions.
Choose the graph representation.
Track algorithm state and handle disconnected/cyclic cases explicitly.
Read a tiny input by hand and write down the state after every important operation. For Graph Breadth-First Search, the goal is to make the invariant visible rather than to memorize code.
function bfs(graph, start) {
const seen = new Set([start]);
const queue = [start];
let head = 0;
while (head < queue.length) {
const node = queue[head++];
for (const next of graph[node] ?? []) {
if (!seen.has(next)) {
seen.add(next);
queue.push(next);
}
}
}
return seen;
}不要死记语法。跟踪每一行中发生变化的状态，并把它与上面描述的不变量联系起来。
O(V+E)
Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.
适用场景
- Use the algorithm only when its graph assumptions match the problem.
通常哪里会出错
- Forgetting disconnected components.
- Mixing weighted and unweighted shortest-path algorithms.
- Not protecting against revisits/cycles.
专业回答结构
The queue is not an implementation detail—it creates level order, which is exactly why unweighted shortest paths work.
What problem does Graph Breadth-First Search solve?
BFS explores a graph level by level using a queue. In an unweighted graph it finds shortest paths by number of edges.
关于复杂度应该提到什么？
Its typical cost here is O(V+E), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.
最常见的错误是什么？
Forgetting disconnected components.