Java超详细精讲数据结构之bfs与双端队列

什么是BFS？

BFS 是一种广度优先搜索的算法，与其对应的是 DFS (深度优先搜索) 算法。

BFS 的思想是从一个起始状态开始，一层一层向外扩散，直到扩散到目标状态为止。

具体的实现方式是使用队列来存储要扩散的状态，在每次扩散时，先将队首元素出队，然后将该状态的所有子状态入队。入队的操作会保证每个状态只被扩散一次，从而确保BFS的正确性。

在BFS 中，还有一个重要的概念——广度，表示的是从起点到该状态的路径长度，即扩散到该状态需要的步数。扩散到目标状态时，该步数也就是最少步数。这也是 BFS 算法的一个重要应用场景——搜索最短路径问题。

双端队列

双端队列是一种具有队列和栈的特点的线性数据结构。

它支持在队列头部和尾部进行插入和删除操作，因此可以同时支持FIFO和LIFO两种操作方式，使得双端队列在某些算法中更易于使用。

使用Java语言实现双端队列时，我们可以使用LinkedList来实现，它已经实现了Deque接口。

BFS与双端队列的结合

BFS算法在执行过程中，需要不断将状态加入队列并出队，这显然需要使用队列这种数据结构。但是，当需要在队列头部和尾部进行插入和删除操作时，使用普通的队列就显得不太方便。

这时，双端队列就派上用场了——可以将队列定义为双端队列，然后在需要在队列头部和尾部进行操作时，直接调用双端队列的方法即可。

在具体的实现中，我们可以将每个要扩散的状态封装为一个类，然后定义一个变量表示该状态的广度，方便后续的最短路径查询。

下面是一个BFS算法与双端队列的示例代码：

import java.util.*;

public class BFS{

    static class State {
        int num;
        int depth;
        State(int num, int depth) {
            this.num = num;
            this.depth = depth;
        }
    }

    public static void main(String[] args) {
        Deque<State> deque = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        deque.offer(new State(0, 0));
        visited.add(0);

        while (!deque.isEmpty()) {
            State p = deque.poll();
            if (p.num == 10) {
                System.out.println(p.depth);
                return;
            }

            int num1 = p.num + 1;
            if (!visited.contains(num1)) {
                visited.add(num1);
                deque.offer(new State(num1, p.depth + 1));
            }

            int num2 = reverse(p.num);
            if (!visited.contains(num2)) {
                visited.add(num2);
                deque.offer(new State(num2, p.depth + 1));
            }
        }
    }

    private static int reverse(int num) {
        int res = 0;
        while (num != 0) {
            res = res * 10 + num % 10;
            num /= 10;
        }
        return res;
    }
}

在上面的示例中，我们通过 BFS 算法求解了从0到10的最短路径，并使用了双端队列来实现队列的操作。

再举一个更实际的例子，比如我们需要在一个迷宫里搜索从起点到终点的最短路径。这时，我们可以将每一个位置都看作是一个状态，然后使用 BFS 算法来搜索。

在具体的实现中，我们可以使用双端队列来存储要进行扩散的状态，从而方便地在队头和队尾进行操作。

import java.util.*;

public class BFS {

    static class Pos {
        int x, y;
        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        int[][] maze = {
                {0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 1, 1, 1, 0, 1, 0},
                {0, 0, 0, 0, 0, 0, 1, 0},
                {0, 1, 1, 1, 1, 1, 1, 0},
                {0, 1, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 1, 1, 1, 1, 0},
                {0, 1, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 1, 1, 1, 0},
                {0, 0, 0, 0, 0, 0, 0, 0}
        };
        int n = maze.length, m = maze[0].length;
        Pos start = new Pos(1, 6);
        Pos end = new Pos(7, 1);

        Deque<Pos> deque = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        deque.offer(start);
        visited.add(start.x + "," + start.y);

        int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

        while (!deque.isEmpty()) {
            Pos p = deque.poll();
            for (int[] dir : dirs) {
                int x = p.x + dir[0];
                int y = p.y + dir[1];
                if (x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0) {
                    String pos = x + "," + y;
                    if (!visited.contains(pos)) {
                        visited.add(pos);
                        deque.offer(new Pos(x, y));
                    }
                }
            }
            if (p.x == end.x && p.y == end.y) {
                System.out.println("找到终点");
                return;
            }
        }

        System.out.println("无法到达终点");
    }
}

在上述示例中，我们使用了 BFS 算法和双端队列，来搜索从起点到终点的最短路径。为了方便表示每个状态，我们使用了 Pos 类来存储位置信息，并使用了一个字符串形式的 visited 集合来表示已经访问过的状态。