2026/4/4

01 BFS（0-1 Breadth-First Search）
通俗说：专门解决边权只有 0 或 1 的图的最短路算法，比普通 BFS 更快，比 Dijkstra 简单。

1. 什么时候用 01 BFS？
   满足下面两点就可以用：
   求无权 / 边权只有 0 和 1的图的最短路
   图是有向或无向都可以
2. 为什么叫 01 BFS？
   因为它用 deque（双端队列）：
   走到边权 = 0 的点：从队头加入
   走到边权 = 1 的点：从队尾加入
   这样保证队列始终保持距离从小到大，和普通 BFS 一样，每个点只需要更新一次最短路。
3. 和普通 BFS、Dijkstra 的区别
   表格
   方式 适用边权 数据结构 时间复杂度
   普通 BFS 只有 1 queue O(n)
   01 BFS 0 或 1 deque O(n)
   Dijkstra 任意非负 优先队列 O(n log n)
4. 核心代码逻辑（记住这个）
   cpp
   运行
   // 初始化距离为无穷大
   dist[] = INF
   dist[start] = 0

deque dq;
dq.push_front(start);

while (!dq.empty()) {
int u = dq.front();
dq.pop_front();

for (每个邻边 u -> v，边权 w) {if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;if (w == 0) {dq.push_front(v);  // 权0放前面} else {dq.push_back(v);   // 权1放后面}}
}

}
5. 直观理解
权为 0：相当于原地瞬移，和当前点同一层，放队头
权为 1：相当于走一步，下一层，放队尾
队列永远保持距离从小到大有序，所以能正确求出最短路。
6. 典型应用场景
网格图中：走空地代价 0，穿墙代价 1
翻转边方向：不翻转 0，翻转 1
0-1 最短路模型