一、引入：为什么需要双端队列广搜？
在普通 BFS 中，我们通常用一个普通队列 Queue 来维护待扩展的状态。
普通 BFS 适用于：
每走一步的代价都相同，比如每次移动的代价都是 1。
例如在网格中，从起点走到终点，每次上下左右移动都算一步，这种问题可以直接用 BFS 求最短步数。
但是有些题目中，每次转移的代价不一定相同，可能是：
有的转移代价是 0
有的转移代价是 1这时候普通 BFS 就不一定正确了。
比如：
从 A 到 B 代价为 1
从 A 到 C 代价为 0
从 C 到 B 代价为 0如果普通 BFS 按“层数”扩展，可能会先认为 A 到 B 的距离是 1，但实际上 A -> C -> B 的总代价是 0。
这类问题就需要使用 双端队列广搜，也叫：0-1 BFS
二、什么是 0-1 BFS？
1. 核心定义
0-1 BFS 是一种用于解决边权只有 0 和 1 的最短路算法。
它可以看作是：
普通 BFS 和 Dijkstra 的中间形态它比普通 BFS 更强，因为它能处理 0/1 边权。
它比 Dijkstra 更简单、更快，因为它不需要优先队列，只需要一个双端队列。
2. 适用条件
0-1 BFS 适用于以下问题：
图中的边权只有 0 和 1也就是说，从一个状态转移到另一个状态时，代价只能是：0 或 1
常见场景包括：
1. 当前操作不消耗代价，记为 0
2. 当前操作需要额外付出一次代价，记为 1
3. 顺着某个方向走代价为 0，改变方向代价为 1
4. 使用已有道路代价为 0，新建道路代价为 1
5. 某些特殊移动免费，普通移动花费 1三、普通 BFS、0-1 BFS、Dijkstra 的区别
可以在博客中放一个对比表：
其中：
V 表示点数
E 表示边数0-1 BFS 的优势是：
在边权只有 0 和 1 的情况下，它可以用 O(V + E) 的复杂度求最短路。四、核心思想
1. 为什么要用双端队列？
双端队列 Deque 的特点是：
可以从队头插入
也可以从队尾插入
可以从队头弹出在 0-1 BFS 中：
如果边权是 0，就把新状态放到队头
如果边权是 1，就把新状态放到队尾也就是：
代价低的状态优先处理
代价高的状态稍后处理2. 为什么边权为 0 要放队头？
假设当前状态的距离是 dist[x]。
如果有一条边：
x -> y，边权为 0那么：
dist[y] = dist[x]也就是说，y 和当前状态的距离一样短。
所以它应该尽快被处理，因此放到队头。
3. 为什么边权为 1 要放队尾？
如果有一条边：
x -> y，边权为 1那么：
dist[y] = dist[x] + 1它的距离比当前状态大 1。
所以它的优先级低一些，可以放到队尾，等当前这一层更优的状态处理完之后再处理。
五、算法流程
0-1 BFS 的整体流程如下：
1. 初始化 dist 数组，所有点的距离设为 INF
2. 起点距离设为 0
3. 将起点加入双端队列
4. 每次从队头取出一个状态
5. 遍历它的所有邻居
6. 如果可以松弛距离：
- 如果边权是 0，把邻居加入队头
- 如果边权是 1，把邻居加入队尾
7. 最后 dist[target] 就是最短距离六、伪代码
dist[start] = 0
deque.push_front(start)
while deque is not empty:
u = deque.pop_front()
for each edge u -> v with weight w:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
if w == 0:
deque.push_front(v)
else:
deque.push_back(v)其中 w 只能是：0 或 1
七、图结构版本
import java.util.*;
public class ZeroOneBFS {
static class Edge {
int to;
int weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
static final int INF = 0x3f3f3f3f;
public static int zeroOneBFS(List<Edge>[] graph, int start, int target) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, INF);
Deque<Integer> deque = new ArrayDeque<>();
dist[start] = 0;
deque.offerFirst(start);
while (!deque.isEmpty()) {
int cur = deque.pollFirst();
for (Edge edge : graph[cur]) {
int next = edge.to;
int weight = edge.weight;
if (dist[next] > dist[cur] + weight) {
dist[next] = dist[cur] + weight;
if (weight == 0) {
deque.offerFirst(next);
} else {
deque.offerLast(next);
}
}
}
}
return dist[target];
}
}八、网格图版本
很多算法竞赛题会把问题放在二维网格中，比如迷宫、地图、方向转换等。
网格图中通常需要：
dist[i][j] 表示从起点到 (i, j) 的最小代价import java.util.*;
public class ZeroOneBFSGrid {
static final int INF = 0x3f3f3f3f;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static int zeroOneBFS(int[][] grid, int startX, int startY, int targetX, int targetY) {
int m = grid.length;
int n = grid[0].length;
int[][] dist = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(dist[i], INF);
}
Deque<int[]> deque = new ArrayDeque<>();
dist[startX][startY] = 0;
deque.offerFirst(new int[]{startX, startY});
while (!deque.isEmpty()) {
int[] cur = deque.pollFirst();
int x = cur[0];
int y = cur[1];
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
continue;
}
int weight = getWeight(grid, x, y, nx, ny);
if (dist[nx][ny] > dist[x][y] + weight) {
dist[nx][ny] = dist[x][y] + weight;
if (weight == 0) {
deque.offerFirst(new int[]{nx, ny});
} else {
deque.offerLast(new int[]{nx, ny});
}
}
}
}
return dist[targetX][targetY];
}
private static int getWeight(int[][] grid, int x, int y, int nx, int ny) {
// 根据题意决定移动代价
//这里只是示例
return 1;
}
}九、经典例子：改变方向的最小代价
1. 问题描述
假设有一个网格，每个格子中有一个方向箭头。
从当前格子出发，如果你按照箭头方向移动，代价为 0。
如果你不按照箭头方向移动，需要修改方向，代价为 1。
问从左上角走到右下角的最小代价是多少？
2. 为什么适合 0-1 BFS？
每次移动只有两种情况：
顺着箭头走：代价 0
不顺着箭头走：代价 1因此边权只有 0 和 1，正好适合 0-1 BFS。
3. 转移方式
假设四个方向编号为：
1：右
2：左
3：下
4：上如果当前格子的方向和本次移动方向一致：
weight = 0否则：
weight = 14. 示例代码
import java.util.*;
class Solution {
static final int INF = 0x3f3f3f3f;
public int minCost(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dist = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(dist[i], INF);
}
// 方向顺序：右、左、下、上
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
Deque<int[]> deque = new ArrayDeque<>();
dist[0][0] = 0;
deque.offerFirst(new int[]{0, 0});
while (!deque.isEmpty()) {
int[] cur = deque.pollFirst();
int x = cur[0];
int y = cur[1];
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
continue;
}
// grid[x][y] 的方向编号是 1 到 4
// k 的编号是 0 到 3，所以要用 k + 1 进行比较
int weight = grid[x][y] == k + 1 ? 0 : 1;
if (dist[nx][ny] > dist[x][y] + weight) {
dist[nx][ny] = dist[x][y] + weight;
if (weight == 0) {
deque.offerFirst(new int[]{nx, ny});
} else {
deque.offerLast(new int[]{nx, ny});
}
}
}
}
return dist[m - 1][n - 1];
}
}十、正确性理解
0-1 BFS 的关键在于：
双端队列中靠前的状态，一定不会比靠后的状态距离更大。因为每次扩展状态时，新的边权只有两种：0 或 1
如果是 0，说明新状态的距离和当前状态一样，因此放到队头。
如果是 1，说明新状态的距离比当前状态多 1，因此放到队尾。
这样就近似实现了 Dijkstra 中“小距离优先”的思想。
但因为边权只有 0 和 1，所以不需要优先队列，只需要双端队列即可。
十一、复杂度分析
设点数为 V，边数为 E。
每条边在松弛时最多被有效处理有限次，因此整体复杂度为：
时间复杂度：O(V + E)
空间复杂度：O(V)如果是二维网格，假设行数为 m，列数为 n，每个格子最多有 4 条边，则：
点数 V = m * n
边数 E ≈ 4 * m * n所以复杂度可以写成：
时间复杂度：O(m * n)
空间复杂度：O(m * n)十二、和 Dijkstra 的关系
0-1 BFS 本质上可以看成是 Dijkstra 在特殊边权下的优化版本。
Dijkstra 的做法是：
每次从优先队列中取出当前距离最小的点0-1 BFS 的做法是：
使用双端队列维护相对有序的状态因为边权只有 0 和 1，所以当前点扩展出去的新距离只可能是：
dist[cur]
dist[cur] + 1因此双端队列就足够维护顺序。
如果边权不是 0 和 1，而是普通非负数，比如 2、5、10，那么就不能使用 0-1 BFS，应该使用 Dijkstra。
十三、常见错误
1. 把 0-1 BFS 写成普通 BFS
错误写法：
queue.offer(next);这样会丢失“0 权边优先”的性质。
正确写法：
if (weight == 0) {
deque.offerFirst(next);
} else {
deque.offerLast(next);
}2. 使用 visited 数组过早标记
普通 BFS 中经常使用：
visited[next] = true;但在 0-1 BFS 中，不推荐一开始就用 visited 直接锁死状态。
因为一个点可能先被较差距离访问，之后又被更短距离更新。
更稳妥的写法是只依赖 dist 松弛：
if (dist[next] > dist[cur] + weight) {
dist[next] = dist[cur] + weight;
}3. 忘记初始化 dist
最短路问题中，dist 必须初始化为一个很大的数：
Arrays.fill(dist, INF);起点初始化为：
dist[start] = 0;4. 边权判断写反
尤其是网格方向题中，容易把方向编号弄错。
例如：
int weight = grid[x][y] == k + 1 ? 0 : 1;这里要确认题目中的方向编号和自己数组中的方向顺序是否一致。
5. 把不适合的问题强行用 0-1 BFS
0-1 BFS 只能处理：边权为 0 或 1 的最短路
如果边权可能是：2、3、5、10
就不能直接用 0-1 BFS。
这时应该考虑：Dijkstra
搜索算法专题：双端队列广搜，0-1 BFS
本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
评论交流
欢迎留下你的想法