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; } }