广度优先搜索

(Updated: )
数据结构与算法

BFS

广度优先搜索的搜索过程有点像一层一层地进行遍历，每层遍历都以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。需要注意的是，遍历过的节点不能再次被遍历。

第一层

  • 0 -> {6,2,1,5};

第二层

  • 6 -> {4}
  • 2 -> {}
  • 1 -> {}
  • 5 -> {3}

第三层

  • 4 -> {}
  • 3 -> {}

可以看到，每一层遍历的节点都与根节点距离相同。设 di 表示第 i 个节点与根节点的距离，推导出一个结论: 对于先遍历的节点 i 与后遍历的节点 j，有 di<=dj。利用这个结论，可以求解最短路径等 最优解 问题: 第一次遍历到目的节点，其所经过的路径为最短路径。应该注意的是，使用 BFS 只能求解无权图的最短路径。

在程序实现 BFS 时需要考虑以下问题:

  • 队列: 用来存储每一轮遍历得到的节点；
  • 标记: 对于遍历过的节点，应该将它标记，防止重复遍历。

迷宫问题

题目描述：有一个 n * m 的迷宫，求从迷宫左上角到右下角的最短路径。

1
2
3
4
5
6
1 1 0 1 
1 1 0 1 
0 1 1 0 
1 1 1 1 

1表示可以通过，0表示障碍物，求解从（0，0）到（x，y）的最短路径是多少。

解决

一层一层进行枚举（按照上右下左的方向）

  1. 第一层
    • [0,0]->{[0,1],[1,0]}
  2. 第二层
    • [0,1]->{[1,1]}
    • [1,0]->{}
  3. 第三层
    • [1,1]->{[2,1]}
  4. 第四层
    • [2,1]->{[2,2],[3,1]}
  5. 第五层
    • [2,2]->{[3,2]}
    • [3,1]->{[3,0]}
  6. 第六层
    • [3,2]->{[3,3]} -end
    • [3,0]->{}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class BFSTest {

    //迷宫地图的二维数组
    static int[][] map = {{1, 1, 0, 1}, {1, 1, 0, 1}, {0, 1, 1, 0}, {1, 1, 1, 1}};
    //记录当前位置有没有被访问过
    static int[][] temp = new int[100][100];
    //按照上右下左的方向遍历迷宫
    static int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public static int bfs(int[][] map) {
        int m = map.length;
        int n = map[0].length;
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(0, 0));
        int len = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            len++;
            while (size-- > 0) {
                Pair<Integer, Integer> cur = queue.poll();
                int cr = cur.getKey();
                int cc = cur.getValue();
                if (temp[cr][cc] == 1) {
                    continue;
                }
                //判断是否到达终点，并返回len
                if (cr == m - 1 && cc == n - 1) {
                    return len;
                }
                //当前位置标记为访问过
                temp[cr][cc] = 1;
                for (int[] d : direction) {
                    int nr = cr + d[0];
                    int nc = cc + d[1];
                    //判断是否越界
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                        continue;
                    }
                    if (map[nr][nc] == 1 && temp[nr][nc] == 0) {
                        queue.offer(new Pair<>(nr, nc));
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int res = bfs(map);
        System.out.println(res);
    }

}