BFS问题
简介
BFS，英文全称是 Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）
我的理解
最早我学广度优先遍历是在二叉树里面的 层序遍历， 广度优先搜索的做法是
1.首先创建一个队列（queue）,
2.把根节点的存入队列
3.将根节点(root)取出，然后取出 root.left和root.right放到队列里面 （这样的作用是遍历每一层）(如下图)
4.然后取出root.left,root.right取出下一层节点，也就是子节点，让后将这些子节点放在队列里面
4.重复上述操作，直到所有的节点被取出
代码实现：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
//设置优先队列
Queue<TreeNode> queue = new ArrayDeque<>();
//层序遍历
if (root != null) {
queue.add(root);
}
//开始进行层序遍历
//层序遍历临界条件是：队列不为空，也就是没有遍历完成
while (!queue.isEmpty()){
//获取当前队列的长度
int n = queue.size();
List<Integer> num = new ArrayList<>();
for (int i = 0; i < n; i++) {
//先从队列里面取出来这些值
TreeNode poll = queue.poll();
//加入num，然后进行左右字数的遍历
num.add(poll.val);
if (poll.left!=null){
//将左右子树加入优先队列
queue.add(poll.left);
}
if (poll.right!=null){
//将左右子树加入优先队列
queue.add(poll.right);
}
}
res.add(num);
}
return res;
}
下面几个实例BFS
463.岛屿的周长
题目:
思路：
暴力破解，直接遍历为1的岛屿四个方向有多少处水域或者边界，初始化默认周围都是水域（count=4），如果检测的四个方向有若干个岛屿，那么这个岛屿的周长的count就需要（减岛屿的数量）
ps:注意 需要在地图外边套一层数据，目的是为了防止数组在判断四个方向的时候发生越界
代码：
class Solution {
public int islandPerimeter(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] num = new int[n+2][m+2];
int numCount = 0;
for (int i = 1; i <n+1 ; i++) {
for (int j = 1; j <m+1 ; j++) {
num[i][j] = grid[i-1][j-1];
}
}
for (int i = 1; i <n+1 ; i++) {
for (int j = 1; j <m+1 ; j++) {
if (num[i][j]==1){
numCount+=RoundLong(num,i,j);
}
}
}
return numCount;
}
public int RoundLong(int[][] num,int i,int j){
int count = 4;
if (num[i-1][j]==1){
count--;
}
if (num[i-1][j]==1){
count--;
}
if (num[i][j-1]==1){
count--;
}
if (num[i][j+1]==1){
count--;
}
return count;
}
}
思路二：
找规律+BFS，通过观察我们发现，当岛屿和岛屿边界之间就不会产生边，岛屿和黑色边界或者岛屿和蓝色海洋会产生一条边，我们就可以通过bfs挨个找岛屿并且判断，进而计算周长
代码：
class Solution {
public static int islandPerimeter(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
return dfs(grid, i, j);
}
}
}
return 0;
}
public static int dfs(int[][] grid, int i, int j) {
//如果从岛屿走到网格边界，那么++
if (!(i >= 0 && i < grid.length && j >= 0 && j < grid[i].length)) {
return 1;
}
//如果从岛屿走向海域，那么++
if (grid[i][j] == 0) {
return 1;
}
//如果已经走过就不让他走了,标记为2就返回为0了
if (grid[i][j] != 1) {
return 0;
}
//如果还有进行状态的变换，将当前岛屿置位2
grid[i][j] = 2;
return dfs(grid, i-1, j) +
dfs(grid, i+1, j) +
dfs(grid, i, j-1) +
dfs(grid, i, j+1);
}
}
200.岛屿数量
题目：
思路：
和上面岛屿的周长模板一样，只不过需要在四个方向进行标记，标记完了之后需要让Count++，最后统计Count个数即可
代码：
class Solution {
public int numIslands(char[][] grid) {
int numCount = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
//进行dfs判断
if (grid[i][j] == '1') {
dfs(grid, i, j);
numCount++;
}
}
}
return numCount;
}
//目的，遍历数组并且修改数组为2
public void dfs(char[][] grid, int i, int j) {
//首先标记从这块进行引申的所有区域
//如果发生越界那么就返回0
if (!(i >= 0 && i < grid.length && j >= 0 && j < grid[i].length)) {
return;
}
//如果相邻的节点为1,那么就继续遍历
//不为1就返回
if (grid[i][j] != '1') {
return;
}
//标记为2
grid[i][j] = 2;
//四个方向进行遍历和标记
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}
695.岛屿的最大面积
题目：
思路：
每次找到一个岛屿然后，进行bfs，寻找四个方向的岛屿，然后每次找到一个岛屿让count++ , 最后返回count进行比较，找到最大的岛屿
代码：
class Solution {
public static int maxAreaOfIsland(int[][] grid) {
int numCount = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
//进行dfs判断
if (grid[i][j] == 1) {
numCount = Math.max(numCount,dfs(grid,i,j));
}
}
}
return numCount;
}
public static int dfs(int[][] grid, int i, int j) {
int count = 0;
//首先标记从这块进行引申的所有区域
//如果发生越界那么就返回0
if (!(i >= 0 && i < grid.length && j >= 0 && j < grid[i].length)) {
return 0;
}
//如果相邻的节点为1,那么就继续遍历
//不为1就返回
if (grid[i][j] != 1) {
return 0;
}
//标记为2
grid[i][j] = 2;
count++;
//四个方向进行遍历和标记
count+=dfs(grid, i - 1, j)
+dfs(grid, i + 1, j)
+dfs(grid, i, j - 1)
+dfs(grid, i, j + 1);
return count;
}
}