使用双端队列实现 0-1 BFS
处理边权为 0 或 1 时的最短路径
使用双端队列实现 0-1 BFS 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
一种特殊的图
有些图的边权重只有0 或 1。对于这类图，您可以用一种更简单、更快的技巧击败 Dijkstra。
认识 0-1 BFS
0-1 BFS可以在线性时间内求出边权重为 0 或 1 的图中的最短路径，完全不需要堆，也没有 log 因子。
工具：双端队列
用双端队列替代堆。双端队列可以从队首和队尾添加或弹出元素。
from collections import deque
dq = deque([src])核心思路
权重为 0 的边不会改变距离，而权重为 1 的边会使距离加一。双端队列会按顺序保存这两组节点。
零权边放在队首
经过一条权重为 0 的边后，请对邻居调用appendleft，让它下一个被处理，因为它不会增加距离。
dq.appendleft(v)权重为一的边放在队尾
经过一条权重为 1 的边后，请对邻居调用append将其加入队尾，因为它与源点相隔一层。
dq.append(v)从队首弹出
始终对当前节点调用popleft。这样可以让双端队列按距离排序，就像分层 BFS 一样。
u = dq.popleft()结合权重进行松弛
请松弛每条边：将新距离设为 dist[u] 加上边权，然后根据权重将节点加入队首或队尾。
nd = dist[u] + w
if nd < dist[v]:
dist[v] = nd为什么它能保持有序
双端队列中同时最多只有两个不同的距离。这一不变量正是队首和队尾放置策略有效的原因。
线性时间的速度
由于不需要堆，0-1 BFS 的复杂度为O(V + E)，在同一个图上明显快于 Dijkstra。
何时使用它
只要移动代价是0 或 1，就可以使用它，例如某些步无法通行而其他步可以通行的网格。
快速检查
您通过一条权重为 0 的边松弛了一个邻居。它应该放在哪里？
回顾：0-1 BFS
使用双端队列时，将权重为 0 的边放到队首，将权重为 1 的边放到队尾。这样就能以简洁的 O(V+E) 时间求出最短路径。⚡
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「使用双端队列实现 0-1 BFS」课时是免费的吗？
是的 — 「使用双端队列实现 0-1 BFS」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「使用双端队列实现 0-1 BFS」这节课中我会学到什么？
处理边权为 0 或 1 时的最短路径 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「使用双端队列实现 0-1 BFS」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 使用堆实现 Dijkstra
- 使用双端队列实现 0-1 BFS
- Bellman-Ford 与负权边
- Floyd-Warshall 全点对算法