01BFS 是一种特殊的广度优先搜索（BFS）算法，主要用于解决图中边权仅为 0 或 1 的单源最短路径问题。
它是 Dijkstra 算法在特定条件下的高效变种，时间复杂度可以达到 \(O(V + E)\)（\(V\) 是顶点数，\(E\) 是边数），比通用的 Dijkstra 算法（\(O(E \log V)\)）更快。
1. 01BFS 的原理
在标准的 BFS 中，我们假设所有边的权重都是 1，所以先进入队列的节点距离一定不大于后进入的节点。但在边权包含 0 和 1 时，普通的队列无法保证这种“单调性”。
核心思想：
为了保证队列中节点的距离始终是从小到大排列的：
- 如果当前经过的边权重是 0，说明到达下一个节点的距离没有增加，这个节点应该被优先处理。
- 如果当前经过的边权重是 1，说明到达下一个节点的距离增加了，这个节点按正常顺序排在后面。
实现方式：
使用双端队列（Deque）代替普通队列：
- 如果边权为 0：将新节点插入到队首（
push_front）。 - 如果边权为 1：将新节点插入到队尾（
push_back）。
这样可以确保：在任何时刻，队列中存在的节点，其到起点的距离最多只有两种（设为 \(d\) 和 \(d+1\)），且 \(d\) 一定在 \(d+1\) 之前。
2. 01BFS 与 普通 BFS 的区别
| 特性 | 普通 BFS | 01BFS |
|---|---|---|
| 适用场景 | 所有边权均为 1（或相等且非负） | 边权仅为 0 或 1 |
| 数据结构 | 普通队列 (queue) |
双端队列 (deque) |
| 入队逻辑 | 直接加到队尾 | 0 权边入队首，1 权边入队尾 |
| 更新机制 | 每个节点第一次被访问即是最短路 | 每个节点可能被多次探测，只有发现更短路径时才更新并入队 |
| 时间复杂度 | \(O(V + E)\) | \(O(V + E)\) |
3. 01BFS 与 Dijkstra 的区别
其实 01BFS 可以看作是 Dijkstra 算法的特例优化。
- Dijkstra：使用优先队列（堆）来寻找当前距离最小的节点。每次弹出的复杂度是 \(O(\log V)\)。
- 01BFS：由于边权只有 0 和 1，最小距离节点要么是当前层的（通过 0 权边到达），要么是下一层的（通过 1 权边到达）。使用双端队列可以 \(O(1)\) 地完成维护工作，省去了堆排序的开销。
4. 算法流程 (伪代码)
dist[start] = 0
dq = deque([start])while dq:u = dq.popleft()for v, weight in neighbors[u]:if dist[v] > dist[u] + weight:dist[v] = dist[u] + weightif weight == 0:dq.appendleft(v) # 0权边，插到前面优先处理else:dq.append(v) # 1权边，插到后面
5. 什么时候用 01BFS？
最典型的场景是：“最少代价”问题，且代价的增加不是连续的，而是开关式的。
- 电路板/网格图问题：比如在网格中移动，直走代价为 0，转弯代价为 1，求到达终点的最小转弯次数。
- 开关/翻转问题：比如某些路已经通了（代价 0），某些路需要修理才能通（代价 1），求最少修理次数。
- 双端限制问题：在图中求一条路径，使得路径上满足某种条件的边最少。
总结
01BFS 的精髓在于利用双端队列维护了搜索过程中的单调性，从而在处理 0/1 权值图时，规避了 Dijkstra 堆排序的成本，达到了和普通 BFS 一样的线性时间复杂度。