宽度优先搜索（BFS）

宽度优先搜索算法也可以叫作广度优先搜索算法，两者并无区别。

基本概念

  • 广度优先搜索使用迭代法和队列的操作类似，一般使用队列来实现,由于LinkedList实现了Queue接口，所以一般使用LinkedList来做迭代型BFS

    1
    Queue<> queue = new LinkedList<>();

  • 广度优先搜索是按层搜索

    • 搜索一层时，先将其出队，然后操作，之后将与其有关系的下一层元素入队，直到队列遍历为空
    • 为了知道是否走到过某一个点，就需要使用一个数组来记录是否走到过该位置
    • 在最开始使用bfs方法的函数中需要执行遍历操作，来选取遍历操作的起点。例如：从1位置作为起点开始执行bfs操作，从2位置作为起点开始执行bfs操作

常用题

  1. 与动态规划题类似，但是动态规划题更侧重于数字的最忧，不在意路径；而BFS，DFS解决那种与路径有关的题

代码模板

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
class Soulution {
    boolean[] inq = new boolean[];//记录走过的下标,与待走位置大小一致
    public static void main(String[] args){//主函数，可能不是main函数
        int[] a = new int[];//可以作为起点的数组
        for(int i = 0 ; i< a.length ; i++){
            if(judge(a[i])){
            	bfs(a[i]);
            }
        }
    }
    //执行bfs
    public void bfs(int t) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(t);//一定要先入队，否则队列为空
        while(!queue.isEmpty()){
            int t1 = queue.poll();//先出队操作
            
            需要执行的操作
                
            if(judge(t1.有关系的元素)){
                
            }
        }
    }
    // 判断是否可以执行bfs
    public boolean judge(元素){
        if(元素 in inq) return false;
        
        if(不满足其他限制) return false;
        
        return true;
    }
}

例题

岛屿问题（力扣 200）

题目

1
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围（不能走）

原题连接

200. 岛屿数量 - 力扣（LeetCode）

代码

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
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
    // 坐标
    class Node{
        int x;
        int y;
    }
    // 坐标变化，上下左右
    int[] X = {1,-1,0,0};
    int[] Y = {0,0,1,-1};
    int colsize = 0;// 列数
    int rowsize = 0;// 行数
    boolean[][] inq;// 判断是否入队标记
    public int numIslands(char[][] grid) {
        colsize = grid[0].length;// 获取列数
        rowsize = grid.length;	// 获取行数
        inq = new boolean[rowsize][colsize];// 初始化标记
        int ans = 0;
        
        // 遍历起点操作
        for(int i = 0 ; i < rowsize ; i++ ){
            for(int j = 0 ; j < colsize ; j++ ){
                if(is(i,j,grid)){
                    ans++;
                    bfs(i,j,grid);
                }
            }
        }
        
        return ans;
    }
    
    // 判断是否可以执行bfs 
    public boolean is(int x,int y,char[][] grid){
        if(x >= rowsize || x < 0 || y >= colsize || y < 0) return false;// 这里多一个是否在坐标内的判断条件
        if(inq[x][y] || grid[x][y] == '0') return false;// 判断是否在如果队
        return true;
    }
    
    // 执行bfs
    public void bfs(int x,int y,char[][] grid){
        Node node = new Node();
        // 初始化队列
        Queue<Node> queue = new LinkedList<>();
        node.x = x;
        node.y = y;
        //入队
        queue.offer(node);
        inq[x][y] = true;
        while(!queue.isEmpty()){
            //出队
            Node top = queue.poll();
            // 遍历上下左右的元素（因为设置了坐标变化的数组，所以可以直接遍历）
            for(int i = 0 ; i < 4 ; i++){
                if(is(top.x+X[i],top.y+Y[i],grid)){
                    Node node1 = new Node();
                    node1.x = top.x + X[i];
                    node1.y = top.y + Y[i];
                    //新元素入队
                    queue.offer(node1);
                    inq[node1.x][node1.y] = true;
                }
            }
        }
        
    }
}

解析

  • 这里使用的bfs操作其实就是遍历是否可以到达而已，所以没有其他多的操作，其他题可能需要判断大小之类的，也会写在bfs函数中
  • 这个题的特殊点是结点元素是坐标，涉及到上下左右移动，使用到定义一个类来处理每个点的坐标的x和y的想法来判断坐标

相同树（力扣 100）

题目

1
2
给你两棵二叉树的根节点 p和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

原题链接

100. 相同的树 - 力扣（LeetCode）

代码

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
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null && q != null || p != null && q == null) return false;
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(p);
        queue2.offer(q);
        while(!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if(node1.val != node2.val) return false;
            TreeNode left1 = node1.left , right1 = node1.right, left2 = node2.left,right2 = node2.right;
            if((left1 == null ^ left2 == null) || (right1 == null ^ right2 == null)) return false;
            if(left1 != null){ 
                queue1.offer(left1);
                queue2.offer(left2);
            }
            if(right1 != null){
                queue1.offer(right1);
                queue2.offer(right2);
            }
        }
        return queue1.isEmpty() && queue2.isEmpty();//判断是否同时为空，不同时为空那么一定是右一个数的高度比另一个数的高度大，那么两个数就不是相同的数
    }
}

解析

这道题实际上就是用到一种二叉树的遍历方式，用到了前序遍历

二叉树有常用的四种遍历方式：

​ 都可用bfs和dfs的方式遍历

一、前中后序遍历

​ 根据根节点的前中后位置而确定，子节点都是先左后右

1
2
3
前序遍历	根->左->右
中序遍历    左->根->右
后序遍历    左->右->根

二、层序遍历

岛屿的周长（力扣 463）

题目

1
2
3
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

原题链接

463. 岛屿的周长 - 力扣（LeetCode）

代码

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
    int ans = 0;			//结果用静态值来获取
    // 两个控制坐标移动的数组
    int[] X = {-1,1,0,0};
    int[] Y = {0,0,-1,1};
    // 得到grid的行数和列数
    int row = 0,col = 0;
    // 坐标类
    class Point{
        int x;
        int y;
        public Point(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
    // 这个很重要，记录是否找到了第一个陆地
    boolean isBegin = false;

    // 主方法
    public int islandPerimeter(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        for(int i = 0 ; i < row ; i++){
            for(int j = 0 ; j < col ; j++){
                if(judge(i,j,grid)){
                    bfs(i,j,grid);
                    return ans;
                }
            }
        }
        return 0;
    }

    // 判断是否是陆地，即是否可以将这块坐标放进队列中
    public boolean judge(int x,int y,int[][] grid){
        //下标越界
        if(x < 0 || x >= row || y < 0 || y >= col) {
            ans++;
            return false;
        }
        // 下标不越界
        if(grid[x][y] == 1){
            if(!isBegin)
                isBegin = true;
            return true;
        }
        else if(grid[x][y] == 0 && isBegin) ans++;
        return false;
    }

    // bfs代码
    public void bfs(int x,int y,int[][] grid){
        Queue<Point> queue = new LinkedList<>();
        Point oldPoint = new Point(x,y);
        queue.offer(oldPoint);
        grid[x][y] = 2;
        while(!queue.isEmpty()){
            Point oldPoint1 = queue.poll();
            for(int i = 0 ; i < 4 ; i++ ){
                int newX = oldPoint1.x + X[i];
                int newY = oldPoint1.y + Y[i];
                if(judge(newX,newY,grid)){
                    Point newPoint = new Point(newX,newY);
                    queue.offer(newPoint);
                    grid[newX][newY] = 2;
                }
            }
        }
    }
}

解析

这个做法时间复杂度不占优势，但空间复杂度较低

这道题的重点思想是：

  • 利用ans作为全局变量来记录边的值
  • 如果访问到坐标下标越界了就给ans加一，既然下标越界了，那么就不能到达，所以返回false
  • 如果访问到坐标下标没有越界则判断值，如果是1则表示新岛，就直接返回true，表示可以添加这块岛
  • 如果访问到的值是0则表示是水，ans可加以，但是要返回false，因为是水，坐标不能到

这道题就几个巧妙的地方：

  • 不需要再新建一个inq来储存是否入队了，只要入队就将原本的值改为2或除了1，0的其他值
  • 直接在坐标类中添加构造方法，会减少代码量，但时空间复杂度是否会增加还不确定
  • 只有一个岛，那么找到一个数值为1的块开始bfs就可以了，执行完bfs就可直接返回结果

关键代码：

1
boolean isBegin = false;
1
2
3
4
5
6
7
8
for(int i = 0 ; i < row ; i++){
    for(int j = 0 ; j < col ; j++){
        if(judge(i,j,grid)){
            bfs(i,j,grid);
            return ans;
        }
    }
}
1
2
3
4
5
6
if(grid[x][y] == 1){
    if(!isBegin)
        isBegin = true;
    return true;
}
else if(grid[x][y] == 0 && isBegin) ans++;

因为只有一个导，但是要反复遍历是不是岛的一块陆地，判断函数会更具是否越界和是否是水来添加边数，如果是水，但还没有找到岛，这种情况是不能让ans++的。说以设计了一个isBegin的全家变量，记录找到第一块陆地的前后，只有在找到了第一块陆地之后，遇到水才会增加边数。

这道题的bfs代码几乎都是入队和出队操作，只是将对应位置的值做了更改而已，减少了inq的空间开销。

找树左下角的值（力扣 513）

题目

1
2
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

原题链接

513. 找树左下角的值 - 力扣（LeetCode）

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            if(root.right != null) queue.offer(root.right);
            if(root.left != null) queue.offer(root.left);
        }
        return root.val;
    }
}

解析

就是一个简单的遍历问题，但是因为要找左下角的值，所以要尽量先放右子节点