使用 BFS 求无权最短路径
逐层计算从源点出发的距离
使用 BFS 求无权最短路径 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
BFS 的作用
BFS 会按环状层次探索图：先访问起点，再访问距离一步的所有节点，然后是距离两步的节点，依此类推。🌊
为什么按环探索意味着最短
由于 BFS 会先完成当前一层再进入下一层，因此它第一次到达某个节点时，得到的就是到该节点的最短无权路径。
队列是核心
BFS 使用队列：先进先出。您将新的邻居添加到队尾，接着处理队首的节点。
from collections import deque
q = deque([start])记录已经访问的节点
保留一个已访问标记，确保不会将同一个节点加入队列两次。这样可以让 BFS 保持快速并最终结束。
visited = [False] * (n + 1)
visited[start] = True存储距离
一个距离数组保存每个节点所在的层。起点的距离为 0；每个邻居的距离都比其父节点多 1。
dist = [-1] * (n + 1)
dist[start] = 0弹出队首
每一步都取出队列队首的节点。它是距离最近的未处理节点，因此现在就处理它。
u = q.popleft()扩展邻居
对于 u 的每个尚未访问的邻居，将其标记，设置距离，然后将其加入队尾。
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)完整循环
只要队列不为空，就持续弹出节点并扩展其邻居。队列清空时，所有可达节点都已经访问完毕。
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)入队时标记
应在将节点加入队列的瞬间设置已访问标记，而不是等到弹出时再设置。延迟标记会让重复节点进入队列。
不可达节点保持为 -1
BFS 结束后，任何仍保存距离 -1 的节点都表示它从起点不可达。这个结果同样具有意义。
BFS 是线性的
BFS 会恰好访问每个节点和每条边一次，因此运行时间为 O(n + m)。这足以轻松满足大多数竞赛限制。
快速检查
为什么普通 BFS 能得到最短路径？
回顾
您可以使用队列和距离数组运行 BFS：入队时标记，扩展邻居，并在结束时读取最短距离。🎉
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「使用 BFS 求无权最短路径」课时是免费的吗？
是的 — 「使用 BFS 求无权最短路径」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「使用 BFS 求无权最短路径」这节课中我会学到什么？
逐层计算从源点出发的距离 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「使用 BFS 求无权最短路径」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 从输入构建邻接表
- 使用 BFS 求无权最短路径
- DFS、递归与迭代栈
- 连通分量与洪水填充