算法概述
0-1 BFS是专门针对边权仅为0或1的图的最短路径算法。它巧妙地利用双端队列（Deque）替代普通BFS中的普通队列，在O(V+E)时间内完成单源最短路径计算，效率甚至优于Dijkstra算法（O(E log V)）。
本文将深入讲解0-1 BFS的核心思想与正确性证明，并给出完整的Java实现，包含标准版本与扩展应用。
核心思想
问题背景
考虑一个无权图或有特殊结构的图：
– 无权图：所有边权为1，标准BFS即可在O(V+E)内求解
– 0-1权重图：边权仅为0或1，是介于无权图和一般加权图之间的特殊结构
在0-1权重图中，Dijkstra算法使用优先队列，每次操作耗时O(log V)，总复杂度O(E log V)。而0-1 BFS利用边权的特殊性，将复杂度优化到线性O(V+E)。
双端队列的关键作用
0-1 BFS的核心洞察在于：
- 当遍历一条权值为0的边时，目标顶点的距离等于当前顶点的距离（没有增加）
- 当遍历一条权值为1的边时，目标顶点的距离等于当前顶点的距离加1
这意味着：通过权值为0的边到达的顶点，其距离与当前层相同，应该排在队列前端（与当前顶点同层处理）；通过权值为1的边到达的顶点，其距离加1，应该排在队列后端（下一层处理）。
这种特性与标准BFS的完美契合：
– 权值为0的边 → 相当于在同一层扩散 → 加入队首
– 权值为1的边 → 相当于进入下一层 → 加入队尾
正确性证明
引理：在0-1 BFS执行过程中，双端队列中顶点距离值单调不降（从前端到后端）。
证明：
– 初始时队列仅含源点，距离为0，单调性成立
– 假设当前队列满足单调性，考虑从队首取出顶点u：
– 对于权值为0的边(u,v)，dist[v] = dist[u]，加入队首。由于原队首距离就是dist[u]，新加入的v距离也为dist[u]，队首单调性保持
– 对于权值为1的边(u,v)，dist[v] = dist[u]+1，加入队尾。由于队列后端距离 ≥ dist[u]，新加入的dist[u]+1 ≥ 后端距离或成为新的最大值，单调性保持
由数学归纳法，队列单调性始终成立。这意味着从队首取出的顶点距离已经确定（类似Dijkstra的贪心性质），算法正确。
完整Java实现
import java.util.*;
/**
* 0-1 BFS算法：双端队列优化的0-1权重图最短路径
* 时间复杂度: O(V + E)
* 空间复杂度: O(V + E)
*/
public class ZeroOneBFS {
// 无穷大距离值
private static final int INF = Integer.MAX_VALUE / 2;
// 图的邻接表: graph[u] = list of (v, weight) where weight in {0, 1}
private final List<Edge>[] graph;
private final int n;
/**
* 边结构
*/
static class Edge {
int to; // 目标顶点
int weight; // 边权（0或1）
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
/**
* 构造函数
* @param n 顶点数（编号0到n-1）
*/
@SuppressWarnings("unchecked")
public ZeroOneBFS(int n) {
this.n = n;
this.graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
}
/**
* 添加有向边
* @param from 起点
* @param to 终点
* @param weight 边权（必须为0或1）
*/
public void addEdge(int from, int to, int weight) {
if (weight != 0 && weight != 1) {
throw new IllegalArgumentException("0-1 BFS只支持边权为0或1的图");
}
graph[from].add(new Edge(to, weight));
}
/**
* 添加无向边（双向添加）
*/
public void addUndirectedEdge(int u, int v, int weight) {
addEdge(u, v, weight);
addEdge(v, u, weight);
}
/**
* 执行0-1 BFS，返回从源点到所有顶点的最短距离
* @param source 源点编号
* @return 距离数组，不可达为INF
*/
public int[] shortestPath(int source) {
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[source] = 0;
// 访问标记数组，防止重复入队优化
boolean[] inQueue = new boolean[n];
// 双端队列：关键数据结构
ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.addFirst(source);
inQueue[source] = true;
while (!deque.isEmpty()) {
int u = deque.pollFirst();
inQueue[u] = false;
// 遍历u的所有邻接边
for (Edge e : graph[u]) {
int v = e.to;
int w = e.weight;
// 松弛操作
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
// 核心：根据边权选择加入队首还是队尾
if (w == 0) {
// 权值为0：距离不变，加入队首（同层优先处理）
if (!inQueue[v]) {
deque.addFirst(v);
inQueue[v] = true;
}
} else {
// 权值为1：距离加1，加入队尾（下一层处理）
if (!inQueue[v]) {
deque.addLast(v);
inQueue[v] = true;
}
}
}
}
}
return dist;
}
/**
* 带路径记录的0-1 BFS
* @param source 源点
* @return Result对象包含距离数组和前驱数组
*/
public Result shortestPathWithTrace(int source) {
int[] dist = new int[n];
int[] prev = new int[n];
Arrays.fill(dist, INF);
Arrays.fill(prev, -1);
dist[source] = 0;
ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.addFirst(source);
while (!deque.isEmpty()) {
int u = deque.pollFirst();
for (Edge e : graph[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
prev[v] = u;
if (w == 0) {
deque.addFirst(v);
} else {
deque.addLast(v);
}
}
}
}
return new Result(dist, prev);
}
/**
* 路径结果封装
*/
public static class Result {
public final int[] dist;
public final int[] prev;
public Result(int[] dist, int[] prev) {
this.dist = dist;
this.prev = prev;
}
/**
* 重构从source到target的最短路径
*/
public List<Integer> reconstructPath(int source, int target) {
List<Integer> path = new ArrayList<>();
if (dist[target] == INF) {
return path; // 不可达
}
int cur = target;
while (cur != -1) {
path.add(cur);
cur = prev[cur];
}
Collections.reverse(path);
return path;
}
}
// ==================== 测试主程序 ====================
public static void main(String[] args) {
// 示例1：简单的0-1权重图
System.out.println("=== 示例1: 基础0-1权重图 ===");
ZeroOneBFS g1 = new ZeroOneBFS(6);
g1.addEdge(0, 1, 0);
g1.addEdge(0, 2, 1);
g1.addEdge(1, 2, 0);
g1.addEdge(1, 3, 1);
g1.addEdge(2, 3, 0);
g1.addEdge(2, 4, 1);
g1.addEdge(3, 4, 0);
g1.addEdge(3, 5, 1);
g1.addEdge(4, 5, 0);
int[] dist1 = g1.shortestPath(0);
System.out.print("从顶点0出发的最短距离: ");
for (int i = 0; i < dist1.length; i++) {
System.out.print("[" + i + "]=" + (dist1[i] == INF ? "∞" : dist1[i]) + " ");
}
System.out.println();
// 路径重构测试
Result result = g1.shortestPathWithTrace(0);
List<Integer> path = result.reconstructPath(0, 5);
System.out.println("0到5的最短路径: " + path);
System.out.println("路径长度: " + result.dist[5]);
// 示例2：迷宫问题建模（0-1 BFS经典应用）
System.out.println("\n=== 示例2: 迷宫最少转向问题 ===");
solveMazeMinTurns();
// 性能对比测试
System.out.println("\n=== 性能测试: 大规模随机0-1权重图 ===");
performanceTest();
}
/**
* 0-1 BFS经典应用：迷宫最少转向问题
* 在迷宫中，直走代价为0，转向代价为1，求从起点到终点的最少转向数
*/
private static void solveMazeMinTurns() {
// 迷宫: 0=通路, 1=障碍
int[][] maze = {
{0, 0, 0, 0, 1, 0},
{1, 1, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 0}
};
int rows = maze.length;
int cols = maze[0].length;
// 状态: (r, c, dir) 表示在(r,c)朝向dir方向
// dir: 0=上, 1=右, 2=下, 3=左
// 总状态数 = rows * cols * 4
int states = rows * cols * 4;
ZeroOneBFS mazeBfs = new ZeroOneBFS(states);
// 辅助函数：将(r,c,dir)编码为顶点编号
java.util.function.IntBinaryFunction encode = (r, c, dir) ->
(r * cols + c) * 4 + dir;
int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
// 构建图
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (maze[r][c] == 1) continue; // 障碍不可通行
for (int d = 0; d < 4; d++) {
int nr = r + dirs[d][0];
int nc = c + dirs[d][1];
// 边界检查与障碍检查
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (maze[nr][nc] == 1) continue;
int from = (r * cols + c) * 4 + d;
int to = (nr * cols + nc) * 4 + d;
// 沿同一方向前进，转向代价为0
mazeBfs.addEdge(from, to, 0);
// 在(nr,nc)处可以转向其他方向，代价为1
for (int nd = 0; nd < 4; nd++) {
if (nd != d) {
int turnTo = (nr * cols + nc) * 4 + nd;
mazeBfs.addEdge(to, turnTo, 1);
}
}
}
}
}
// 起点(0,0)，终点(4,5)
// 从起点可以向四个方向出发（初始转向代价为0）
int startR = 0, startC = 0;
int targetR = 4, targetC = 5;
// 创建超级源点连接起点所有方向
int superSource = states; // 额外一个顶点
ZeroOneBFS withSource = new ZeroOneBFS(states + 1);
// ... 简化展示，核心思想已说明
System.out.println("迷宫最少转向问题的0-1 BFS建模思路:");
System.out.println(" - 状态: (行, 列, 朝向)");
System.out.println(" - 直走: 边权0（不增加转向次数）");
System.out.println(" - 转向: 边权1（增加一次转向）");
System.out.println(" - 结果: 从起点到终点的最少转向数 = 最短路径距离");
}
/**
* 大规模性能测试
*/
private static void performanceTest() {
int n = 100000;
int m = 500000;
ZeroOneBFS g = new ZeroOneBFS(n);
Random rand = new Random(42);
for (int i = 0; i < m; i++) {
int u = rand.nextInt(n);
int v = rand.nextInt(n);
int w = rand.nextInt(2); // 0或1
g.addEdge(u, v, w);
}
long start = System.currentTimeMillis();
int[] dist = g.shortestPath(0);
long end = System.currentTimeMillis();
int reachable = 0;
for (int d : dist) {
if (d < INF) reachable++;
}
System.out.println("顶点数: " + n);
System.out.println("边数: " + m);
System.out.println("可达顶点数: " + reachable);
System.out.println("运行时间: " + (end - start) + "ms");
}
}
扩展到一般权重图
对于边权仅为0,1,2,…,C的小整数权重图（C为常数），可以使用Dial算法（又称桶Dijkstra），将0-1 BFS扩展到更一般的情况：
/**
* Dial算法：适用于小整数权重（0到C）的最短路径
* 使用C+1个桶替代双端队列，时间复杂度O(C * V + E)
*/
public int[] dialAlgorithm(int source, int maxWeight) {
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[source] = 0;
// 循环桶队列
ArrayDeque<Integer>[] buckets = new ArrayDeque[maxWeight + 1];
for (int i = 0; i <= maxWeight; i++) {
buckets[i] = new ArrayDeque<>();
}
buckets[0].addLast(source);
int currentDist = 0;
int visited = 0;
while (visited < n) {
// 找到当前非空桶
while (currentDist <= maxWeight && buckets[currentDist % (maxWeight + 1)].isEmpty()) {
currentDist++;
}
if (currentDist > maxWeight * n) break; // 所有可达点已处理
int u = buckets[currentDist % (maxWeight + 1)].pollFirst();
if (dist[u] < currentDist) continue; // 已处理过
visited++;
for (Edge e : graph[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
buckets[dist[v] % (maxWeight + 1)].addLast(v);
}
}
}
return dist;
}
复杂度分析
| 算法 | 适用条件 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 标准BFS | 无权图（边权全1） | O(V+E) | O(V+E) |
| 0-1 BFS | 边权为0或1 | O(V+E) | O(V+E) |
| Dial算法 | 边权为0到C的整数 | O(C·V+E) | O(C·V+E) |
| Dijkstra | 非负权图 | O(E log V) | O(V+E) |
| Bellman-Ford | 含负权图 | O(V·E) | O(V+E) |
应用场景
- 网格图路径规划：移动代价只有两种（如免费通道/付费通道）
- 状态转移DP：状态转移代价为0或1的动态规划问题
- 二进制边权网络：网络链路只有高速（权0）和低速（权1）两种
- 最少操作次数：某些问题中操作分为免费操作和代价操作
- 迷宫最少转向：直走免费，转向有代价的游戏AI路径规划
小结
0-1 BFS展示了如何针对问题的特殊结构进行算法优化。通过将边权为0的边对应点加入队首、边权为1的边对应点加入队尾，算法维持了双端队列中距离值的单调性，从而保证了线性时间复杂度。这一思想可以进一步推广到Dial算法处理更一般的小整数权重图。在实际竞赛和工程问题中，识别出0-1权重结构并应用该算法，往往能将运行效率提升一个数量级。
