从一个节点找另一个节点时，路径往往不止一条。若只关心「经过边数最少的路径」，可以从起点开始先看所有一步能到的节点，再看两步能到的节点。这就是广度优先搜索（Breadth-First Search，BFS）的顺序。
以这张有向图为例：
A
↙ ↘
B C
↙ ↘ ↘
D E F从 A 开始，BFS 的访问顺序是 A → B → C → D → E → F。按起点的距离分层看，会更清楚：
距离 0：A
距离 1：B、C
距离 2：D、E、F这里的距离不是坐标上的远近，而是需要经过的边数。例如从 A 到 E 要经过 A → B → E 两条边，距离是 2。
队列如何维持层次
BFS 使用队列（Queue），它遵循先进先出（FIFO）：先放入的节点，先取出。队列中存放的是已经发现、但还没展开其邻居的节点。
从 A 出发时，队列的变化如下：
| 当前取出 | 新发现的节点 | 操作后队列 |
|---|---|---|
A | B、C | B, C |
B | D、E | C, D, E |
C | F | D, E, F |
D | 无 | E, F |
E | 无 | F |
F | 无 | 空 |
B 和 C 都是距离 1 的节点；它们产生的 D、E、F 才是距离 2 的节点。由于 B 先入队，B 的邻居会先排在 C 的邻居前面；但无论相同层级内部的具体顺序如何，距离较小的一层总会先被处理。
这里有两个容易混在一起的时刻：
- 发现节点：第一次看到它，把它标记为已访问并放进队列
- 处理节点：从队首取出它，再查看它的邻居
节点通常在入队时就算“已发现”。队列则保存已经发现、但还没有处理完的节点。
递归函数天然会先沿一条分支走到底，因此更接近 DFS；BFS 的核心不是「循环」，而是这个队列带来的处理顺序。
一个可运行的实现
图通常用邻接表表示：字典的键是节点，值是从它出发能够到达的相邻节点。
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F"],
"D": [],
"E": [],
"F": [],
}
def bfs(graph, start):
queue = deque([start])
visited = {start}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor in visited:
continue
visited.add(neighbor)
queue.append(neighbor)
return order
print(bfs(graph, "A"))
# ['A', 'B', 'C', 'D', 'E', 'F']visited 在节点入队时就写入，而不是等它出队。考虑下面这张有汇合点的图：
A → B
↘ ↓
→ C其中有 A → B、A → C、B → C 三条边。处理 A 时，B 和 C 都会入队；之后处理 B，又会遇到 C。若 C 直到出队才标记，B 会把已经在队列里的 C 再放一次。入队时标记表示“这个节点已经被发现，并且已经排好等待处理”。
visited 也让 BFS 能处理有环图，例如 A → B → C → A。没有它，搜索会沿环持续把同一批节点重新放回队列。
无权图里的最短路径
在所有边代价相同的前提下，BFS 第一次发现某个节点时，走到它的边数已经最少。这个结论来自队列中的层次顺序：
- 起点的距离是
0。 - 处理距离为
d的节点时，新发现的邻居距离是d + 1。 - 距离为
d的节点都排在距离为d + 1的节点前面。
因此，一个节点第一次入队时，不可能还存在一条尚未处理、边数更少的路径。后面即使从别的方向再次遇到它，路径也只会一样长或更长。
这里的「无权」表示每条边的代价相同，可以把每条边都看作长度 1。例如好友关系中的「隔几层好友」、迷宫里每次上下左右移动一格，都是这类问题。若边的代价不同，例如道路有不同长度或时间，普通 BFS 不再保证总代价最小，需要 Dijkstra 等算法。
要记录实际路径，只需在首次发现节点时保存它的前驱：
from collections import deque
def shortest_path(graph, start, target):
queue = deque([start])
previous = {start: None}
while queue:
node = queue.popleft()
if node == target:
break
for neighbor in graph[node]:
if neighbor in previous:
continue
previous[neighbor] = node
queue.append(neighbor)
if target not in previous:
return None
path = []
node = target
while node is not None:
path.append(node)
node = previous[node]
return path[::-1]
print(shortest_path(graph, "A", "E"))
# ['A', 'B', 'E']previous["E"] = "B" 记录了首次到达 E 时来自哪里。最后从目标节点倒着沿前驱回溯到起点，再反转列表，就得到一条最短路径。若有多条同样短的路径，返回哪一条取决于邻接表里的节点顺序。
对 A → B → E 这条结果，前驱记录的形成过程是：
previous[A] = None
previous[B] = A
previous[E] = B从 E 反向读取会得到 E ← B ← A，反转后才是从起点到目标的 A → B → E。
BFS 与 DFS
深度优先搜索（Depth-First Search，DFS）会先沿一条路不断向下，再返回分叉点；它通常借助栈（Stack）或递归。两者都能遍历图，但处理顺序不同。
| 维度 | BFS | DFS |
|---|---|---|
| 扩展方式 | 先处理同一距离的节点 | 先沿一条分支向下 |
| 核心结构 | 队列（FIFO） | 栈（LIFO）或递归 |
| 无权图最短路径 | 第一次到达目标即为最少边数 | 不保证 |
| 常见用途 | 层序遍历、最少步数、连通性 | 路径枚举、拓扑排序、回溯 |
例如在树中，从根节点找最浅的匹配节点，BFS 会最先遇到它；DFS 可能先走进一条很深但并不包含答案的分支。
复杂度与适用边界
设图有 V 个节点、E 条边，使用邻接表时：
- 时间复杂度是
O(V + E)：每个节点最多入队、出队一次，邻接表中的每个边记录检查一次。无向边会在两个端点的列表中各出现一次，仍然记作O(E)。 - 空间复杂度是
O(V)：visited、队列和前驱表在最坏情况下都可能保存所有节点。
在一棵很宽的树里，BFS 的队列会同时保留一整层节点，内存占用可能较高。换来的是按距离扩展的顺序，以及无权图中最短路径这个性质。
图不一定显式画成节点和边。二维网格也可以看成图：每个可走格子是节点，上下左右可走的格子是边；树的层序遍历则是 BFS 在树上的一种形式。它们共享同一个判断方式：从起点按「还差几步」一层层向外展开。