leetcode刷题——之BFS广度优先遍历经典问题

思路

广度优先遍历可以用来看从头走到我要的目的地，需要走几步;

从当前结点开始，每次寻找它相连的所有节点，在每一次遍历完当前节点相邻的所有节点之后，step++，就相当于更深了一层;

要有数组来记录我们已经遍历过的节点，标记节点，防止重复遍历。

基本如下：

//之前把起点先加入队列，定义好队列q,标记数组visited
    while(q not empty) {
    	step++;//更新深度
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            if (cur is target)//到达目的地，返回step值
                return step;
            for (Node x : cur.adj())//将cur的节点挨个加入队列
                if (x not in visited) {//未被遍历过
                    q.offer(x);
                    visited.add(x);
                }
        }
    }
    return -1;

按照这样一个思路，我们可以求解几乎所有有头有尾的路径问题，寻求最短距离。比如二叉树从根到叶子的最小深度，还有如下的岛屿数量问题。

BFS典例：

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
计算岛屿数量，在广度基础上考虑是否越界，以及是否为陆地即数组元素为1；

输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','1','1']
]
输出: 2

代码

含小注释

class Solution {
    int rows;
    int cols;
    private boolean inArea(int x,int y){//考虑是否越界
        return x>=0&&x<rows&&y>=0&&y<cols;
    }
    public int numIslands(char[][] grid) {
        int i,j, k;
        int count = 0;
        rows = grid.length;
        if (rows == 0) {
            return 0;
        }
        cols = grid[0].length;
        boolean [][] marked = new boolean[rows][cols];//标记是否遍历过
        int [][] direction = {{-1,0},{0,-1},{1,0},{0,1}};
        for(i = 0;i<rows;i++){
            for(j = 0;j<cols;j++){
                LinkedList<Integer> queue = new LinkedList<>();
                if(grid[i][j] == '1'&& !marked[i][j]){
                    count++;
                    queue.addLast(i*cols+j);
                    marked[i][j] = true;//入队
                
                    while(!queue.isEmpty()){
                        int cur = queue.removeFirst();
                        int curX = cur/cols;
                        int curY = cur%cols;//控制下一步行走方向
                        for(k = 0;k<4;k++){
                            int newX = curX + direction[k][0];
                            int newY = curY + direction[k][1];
                            if(inArea(newX,newY)&& !marked[newX][newY] &&grid[newX][newY] == '1'){//是陆地，没遍历过，且没越界
                                queue.addLast(newX*cols+newY);
                                marked[newX][newY] = true;
                            }
                        }
                    }
                }
            }
        }
        return count;
    }   
}

本文地址：https://blog.csdn.net/bella_better/article/details/108909875