什么是广度优先搜索 (BFS)？

Question

什么是广度优先搜索 (BFS)？

Accepted Answer

**BFS** 按级别逐层探索图，在深入之前访问节点的所有邻居。它使用 **queue**，并在无权图中找到 **最短路径**（边数最少）。

## 为什么这很重要

从源点开始，将其入队，然后反复出队一个节点，访问其未访问的邻居，并将其入队。`visited` 集合可防止重复访问。

## 例子

```python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()        # FIFO: explore nearest first
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A')                        # -> ['A', 'B', 'C', 'D']
```

## 复杂度

- **时间:** O(V + E) — 每个顶点和边各一次。
- **空间:** O(V) 用于 queue 和 visited 集合。

## 何时使用 / 注意事项

BFS 用于 **无权图中的最短路径**、层序遍历和寻找连通分量。它比 DFS 使用更多内存（一次整个边界）。始终追踪 `visited`，否则可能在有环的情况下永远循环。

## 为什么这很重要

BFS 是当所有边权重相等时寻找最短路径的 *标准* 算法 — 路由、网络爬虫、社交网络度分离。

其基于队列的、逐级的结构是基本的遍历模式。

了解 BFS 与 DFS 的区别可以让你为可达性、路径和排序问题选择合适的工具。