每日算法 — 使用java实现双端队列BFS：0-1权重图的最短路径优化

引言

在图论中，Dijkstra 算法可以求解非负权边的单源最短路径问题，时间复杂度为 O((V+E) log V)。然而，当图中所有边的权重仅为 0 或 1 时，存在一种更优雅的算法——双端队列 BFS（0-1 BFS）。它利用双端队列（Deque）在 O(V + E) 的线性时间内完成求解，无需优先队列的开销。本文将用 Java 实现该算法，并结合迷宫逃生场景进行讲解。

核心思想

0-1 BFS 的关键观察：
– 经过权重为 0 的边时，新距离 不大于 当前节点距离，应放在队列头部
– 经过权重为 1 的边时，新距离 大于 当前节点距离，应放在队列尾部

这样双端队列始终按距离递增顺序存储节点，保证了首次访问即为最短距离，类似于 Dijkstra 但无需堆结构。

算法流程

1. 初始化距离数组 dist[] 为无穷大，dist[start] = 0
2. 将起点放入双端队列
3. 从队首取出节点 u
4. 遍历 u 的所有邻接边 (u, v, w)：
5. 若 dist[u] + w < dist[v]，更新 dist[v]
6. 若 w == 0，将 v 加入队首；若 w == 1，将 v 加入队尾
7. 重复直到队列为空

完整 Java 实现

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * 0-1 BFS 实现：求解 0-1 权重无向图的最短路径
 */
public class ZeroOneBFS {

    /**
     * 图的邻接表边表示
     */
    static class Edge {
        int to;    // 目标节点
        int weight; // 权重（仅 0 或 1）

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    private final int n;              // 节点数量
    private final List<Edge>[] graph; // 邻接表
    private final int INF = Integer.MAX_VALUE / 2;

    @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<>();
        }
    }

    /**
     * 添加无向边
     */
    public void addEdge(int u, int v, int weight) {
        if (weight != 0 && weight != 1) {
            throw new IllegalArgumentException("权重只能是 0 或 1");
        }
        graph[u].add(new Edge(v, weight));
        graph[v].add(new Edge(u, weight));
    }

    /**
     * 0-1 BFS 核心算法
     * @param start 起点
     * @return 从 start 到所有节点的最短距离数组
     */
    public int[] shortestPath(int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        // 双端队列：队首存储距离较小的节点
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offerFirst(start);

        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;

                    // 关键：根据边权重决定加入队首还是队尾
                    if (w == 0) {
                        deque.offerFirst(v); // 0 权边，距离不变，放队首
                    } else {
                        deque.offerLast(v);  // 1 权边，距离+1，放队尾
                    }
                }
            }
        }

        return dist;
    }

    /**
     * 打印最短路径（用于调试）
     */
    public void printPath(int start) {
        int[] dist = shortestPath(start);
        System.out.println("从节点 " + start + " 出发的最短距离:");
        for (int i = 0; i < n; i++) {
            System.out.println("  到节点 " + i + ": " + (dist[i] == INF ? "不可达" : dist[i]));
        }
    }

    /**
     * 迷宫逃生场景：0 表示可通过（权重 0），1 表示需要破墙（权重 1）
     * 求从左上角到右下角的最少破墙次数
     */
    public static int minWallsToBreak(int[][] maze) {
        int rows = maze.length;
        int cols = maze[0].length;
        int n = rows * cols;

        // 将二维坐标映射为一维节点：id = r * cols + c
        ZeroOneBFS solver = new ZeroOneBFS(n);
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int u = r * cols + c;
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                        int v = nr * cols + nc;
                        // 进入目标格子是否需要破墙
                        int weight = maze[nr][nc];
                        // 为避免重复添加，只添加右和下方向的边
                        if (r < nr || c < nc) {
                            solver.addEdge(u, v, weight);
                        }
                    }
                }
            }
        }

        int[] dist = solver.shortestPath(0);
        return dist[n - 1];
    }

    public static void main(String[] args) {
        // 测试一般 0-1 权重图
        ZeroOneBFS graph = new ZeroOneBFS(6);
        graph.addEdge(0, 1, 0);
        graph.addEdge(0, 2, 1);
        graph.addEdge(1, 2, 0);
        graph.addEdge(1, 3, 1);
        graph.addEdge(2, 4, 0);
        graph.addEdge(3, 4, 0);
        graph.addEdge(3, 5, 1);
        graph.addEdge(4, 5, 0);
        graph.printPath(0);
        // 预期：0->0, 1->0, 2->0, 3->1, 4->0, 5->1

        // 测试迷宫场景
        int[][] maze = {
            {0, 1, 0, 0},
            {0, 1, 1, 0},
            {0, 0, 1, 0},
            {1, 0, 0, 0}
        };
        System.out.println("\n迷宫最少破墙次数: " + minWallsToBreak(maze)); // 1
    }
}

复杂度分析

对比 Dijkstra 的 O((V+E) log V)，0-1 BFS 在 0-1 权重场景下完全消除了对数因子，是线性最优算法。

扩展：推广到 0-K 权重

当边权范围为 [0, K] 时，可使用单调队列优化：维护 K+1 个桶（Dial 算法），将节点按距离模 (K+1) 分桶，时间复杂度为 O(K * V + E)。当 K 为常数时仍保持线性。

应用场景

• 迷宫问题：最少破墙次数、传送门与步行混合场景
• 网络路由：链路状态为”畅通”(0) 或”拥塞”(1)
• 图像处理：二值图像中的最短路径（像素值差为 0 或 1）
• 状态转换：状态变化代价为 0 或 1 的自动机最短路径

总结

双端队列 BFS 是 0-1 权重图最短路径问题的最优解。其核心在于利用边的权重视为”距离增量”，通过队首/队尾的插入策略隐式维护了距离单调性。掌握这一技巧，将在面对特定约束的图论问题时，获得比通用算法更优的性能与更简洁的实现。