从一个节点找另一个节点时，路径往往不止一条。若只关心「经过边数最少的路径」，可以从起点开始先看所有一步能到的节点，再看两步能到的节点。这就是广度优先搜索（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 |
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 → C、B → C 这类汇合的边：若 C 直到出队才标记，A 和 B 都可能把 C 放进队列，造成重复处理。入队时标记意味着「这个节点已经被发现，并且已经排好等待处理」。
visited 也让 BFS 能处理有环图，例如 A → B → C → A。没有它，搜索会沿环持续把同一批节点重新放回队列。
无权图里的最短路径
BFS 第一次发现某个节点时，走到它的边数已经最少。原因在于：队列先处理距离较小的节点，而新发现的邻居距离只会比当前节点多 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 时来自哪里。最后从目标节点倒着沿前驱回溯到起点，再反转列表，就得到一条最短路径。若有多条同样短的路径，返回哪一条取决于邻接表里的节点顺序。
BFS 与 DFS
深度优先搜索（Depth-First Search，DFS）会先沿一条路不断向下，再回退到分叉点；它通常借助栈（Stack）或递归。两者都能遍历图，但处理顺序不同。
| 维度 | BFS | DFS |
|---|---|---|
| 扩展方式 | 先处理同一距离的节点 | 先沿一条分支向下 |
| 核心结构 | 队列（FIFO） | 栈（LIFO）或递归 |
| 无权图最短路径 | 第一次到达目标即为最少边数 | 不保证 |
| 常见用途 | 层序遍历、最少步数、连通性 | 路径枚举、拓扑排序、回溯 |
例如在树中，从根节点找最浅的匹配节点，BFS 会最先遇到它；DFS 可能先走进一条很深但并不包含答案的分支。
复杂度与适用边界
设图有 V 个节点、E 条边，使用邻接表时：
- 时间复杂度是
O(V + E)：每个节点最多入队、出队一次，每条边最多检查一次。 - 空间复杂度是
O(V)：visited、队列和前驱表在最坏情况下都可能保存所有节点。
在一棵很宽的树里，BFS 的队列会同时保留一整层节点，内存占用可能较高。换来的是按距离扩展的顺序，以及无权图中最短路径这个性质。
图不一定显式画成节点和边。二维网格也可以看成图：每个可走格子是节点，上下左右可走的格子是边；树的层序遍历则是 BFS 在树上的一种形式。它们共享同一个判断方式：从起点按「还差几步」一层层向外展开。