java算法day25
- 广度优先搜索
- 岛屿数量深搜
- 岛屿数量广搜
广度优先搜索
核心：从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。搜索的方式是上下左右
一张图说明白模拟过程：
每一层，每个点不停的往上下左右的方向扩。
在面对有障碍的情况下也同样如此：
所以可以得出一个结论：
因为bfs这种一圈一圈层层往外搜索的性质，决定了bfs处理得到的路径一定是一条最短路径。
那这种一圈一圈的搜索过程是怎么做到的，用了什么容器才能实现这样的遍历。
回答是：用队列，栈，数组都可以。但是这里习惯用队列。
用队列那就是保证每一圈都是一个方向去转，例如统一顺时针或者统一逆时针。
因为队列是先进先出，加入元素和弹出元素的顺序没有发生改变。
而且顺时针和逆时针转都是可以的，并不用做什么特殊处理。
接下来是一个队列的模板。看看用队列怎么完成bfs。
import java.util.*;
class Solution {
// 表示四个方向：右、下、上、左
private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
// grid 是地图，是一个二维字符数组
// visited 标记访问过的节点，避免重复访问
// x, y 表示开始搜索节点的坐标
public void bfs(char[][] grid, boolean[][] visited, int x, int y) {
//定义队列，该队列用于BFS，其中存的都是点
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y}); // 起始节点加入队列
visited[x][y] = true; // 标记起始节点为已访问
//BFS主循环，当队列不空时，继续搜索
while (!queue.isEmpty()) {
//从队列中把要处理的点取出来，x坐标是cur[0],y坐标是cur[1]。这里把要处理的点的坐标拿出来是为了方便等下做上下左右运算。
int[] cur = queue.poll();
int curx = cur[0];
int cury = cur[1];
// 遍历四个方向：右、下、上、左
//这里相当于处理当前节点，
for (int[] d : dir) {
//为了方便还是计算该节点下一步要走的坐标。分别计算横坐标和纵坐标
int nextx = curx + d[0];
int nexty = cury + d[1];
//这个点算出来了 检查是否越界，看看这个点是否合法
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) {
//如果这里面有一个不满足就代表这个点不合法，那么就不处理，所以跳过处理该方向的点。
continue;
}
//能走到这里说明点是合法的，但是还要看看这个点之前访问过了没。直接通过这个标记数组进行检查即可
// 如果下一个节点没有被访问过，就会进去
if (!visited[nextx][nexty]) {
//然后把这个没访问的节点放入待处理的队列中
queue.offer(new int[]{nextx, nexty});
//然后把该点设置为已经访问
visited[nextx][nexty] = true;
// 在这里可以根据具体问题进行额外的处理
}
//到了这里就会发现，循环里的某方向的一个点处理，而且还把该节点加入到了队列里。因为之后处理这个节点，往外面的方向扩的过程就是上面模拟的bfs。
//这里一个方向就已经处理完毕，下一个循环就是下一个方向了。所以依次类推，就是一圈一圈的往外处理。
//以中间的这个点来模拟，左方向处理完后加入了队列，然后假设转了一圈，跳转下一个节点的时候，从队列里第一个弹出来的节点就是这个左方向的节点，他也是如此的方式进行模拟。
}
}
}
}
我学完这个模板之后，我感觉特别像层序遍历。不过是在图的角度上。
使用这个模板的步骤：
定义问题的网格（grid）。
创建一个与网格大小相同的 visited 数组。
选择起始位置（x, y）。
调用 bfs 方法。
岛屿数量深搜
题目已经说了，只有水平和竖直方向算，斜角度不算连着。这和遍历四个方向的考虑一致了。
算法思想：
1、遍历整个网格
2、当找到一个未访问的陆地时，将岛屿计数+1
3、然后调用DFS标记与这个陆地相连的所有陆地为已访问（用dfs就是递归，但是还是有一点BFS的影子，直接往四个方向都递归，当遇到节点是0就停下，或者节点不合法了也停下）
4、重复这个过程直到遍历完整个网络（相当于把整个网格都处理了。）
这种方法是可以有效的计算岛屿数量，因为每个岛屿只会被计数一次，而与他相连的所有陆地都会在dfs的过程中被标记。
import java.util.Scanner;
public class Main{
//规定四个方向,方便用来计算四个要遍历的方向
static final int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};
//主方法
public static void main(String[] args){
//定义网格
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
grid[i][j] = scanner.nextInt();
}
}
//定义标记网格和计数器
boolean[][] visited = new boolean[n][m];
int result = 0;
//遍历所有网格
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
//遍历的过程中，如果遇到陆地，并且没有访问过，那就意味着这是一个新岛屿，所以先计数器++，然后dfs。把该陆地上所有相邻陆地全部标记为已经访问。
if(!visited[i][j] && grid[i][j]==1){
result++;
//就是dfs这个第一个遇见的陆地，之后会dfs把相邻的陆地全部置为已经访问
dfs(grid,visited,i,j);
}
}
}
//结果输出
System.out.println(result);
}
public static void dfs(int[][] grid,boolean[][] visited,int x,int y){
//这里我写递归出口是已经考虑了，我是遇到了第一个陆地网格才进来的
//所以这里递归出口的条件就会松一点。
if(visited[x][y] || grid[x][y]==0){
return;
}
//先处理当前节点,这里要进行处理就是把他置为true
visited[x][y] = true;
//然后遍历四个方向，每个方向都要进行dfs
for(int[] d:dir){
//dfs之前，把要dfs的坐标算出来
int nextX = x+d[0];
int nextY = y+d[1];
//在进行dfs之前，还要判断这个方向的节点是否合法。
//不合法就跳过了。
if(nextX<0 || nextX>=grid.length || nextY<0 || nextY>=grid[0].length){
continue;
}
//合法就dfs
dfs(grid,visited,nextX,nextY);
}
}
}
岛屿数量广搜版
做这个题的时候，有一个细节需要特别的注意
只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。如果用了后面这种方式，会导致同一节点被多次加入队列。
具体场景如下：
1 1 1
1 1 1
1 1 1
从左上角开始BFS，如果我们在将节点从队列拿出来的时候再去标记。那么
(0,0)加入队列
从队列中取出(0,0)，标记为已经访问
然后BFS将(0,1)和(1,0)加入队列
从队列中取出(0,1)标记为已访问。
然后将(0,1)的邻居(0,2),(1,1)加入队列。
接下来从队列中取出(1,0)然后并标记为已经访问
将(1,0)的邻居加入队列，此时就包含了(1,1)
问题就来了，(1,1)被重复加入队列。
这就是会出现重复的问题，在更大的网格中，这种重复会更加的严重。
队列中会产生大量的重复节点，每个节点会被处理多次，导致算法效率大大降低甚至超时。
所以，应该在加入队列的同时，标记为已经访问。这样当考虑将某点加入队列的时候，发现已经标记过了就不会再重复加入了。
算法思想：
整体来说和DFS的解法一致。就是visited标记那里改成了用bfs的方式来做。
import java.util.*;
public class Main {
private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向
private static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
visited[x][y] = true; // 只要加入队列，立刻标记
//迭代的本质，和层序遍历非常相似，队列不空就不停
while (!queue.isEmpty()) {
//取出节点
int[] cur = queue.poll();
int curx = cur[0];
int cury = cur[1];
//处理四个方向
for (int[] d : dir) {
//计算下一个方向的节点，准备将他加入队列中。
int nextx = curx + d[0];
int nexty = cury + d[1];
//计算出来的这个节点，还要进行安全性判断
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue; // 越界了，直接跳过
//然后再经过是否标记过，是否是岛屿的判断。才能将这个节点标记为true并加入队列
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
queue.offer(new int[]{nextx, nexty});
visited[nextx][nexty] = true; // 只要加入队列立刻标记
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m];
int result = 0;
//算法的核心思想，就是遍历网格。每遇到一个陆地，并且还没访问过
//就统计+1，并且将其相邻陆地按照dfs或者bfs标记为已访问。
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
result++; // 遇到没访问过的陆地，+1
bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
}
}
}
System.out.println(result);
}
}
200 岛屿数量
BFS解法：
class Solution {
int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
public int numIslands(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
boolean[][] visited = new boolean[n][m];
int result = 0;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(!visited[i][j] && grid[i][j]=='1'){
result++;
bfs(grid,visited,i,j);
}
}
}
return result;
}
void bfs(char[][] grid,boolean[][] visited,int x,int y){
//先创建一个队列
Queue<int[]> que = new LinkedList<>();
//第一个节点加入进去，加之前进行标记
visited[x][y] = true;
que.offer(new int[]{x,y});
while(!que.isEmpty()){
//开始取出队列的节点进行处理
int[] cur = que.poll();
int curX = cur[0];
int curY = cur[1];
//然后开始处理该节点的四个方向
for(int[] d : dir){
//通过方向计算该节点的上下左右，然后加入队列中
int nextX = curX+d[0];
int nextY = curY+d[1];
//在加入队列之前还要进行合法性判断
if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length){
continue;
}
//还要判断该节点有没有访问过，并且是不是陆地节点
if(!visited[nextX][nextY] && grid[nextX][nextY] == '1'){
visited[nextX][nextY] = true;
que.offer(new int[]{nextX,nextY});
}
}
}
}
}
DFS解法：
class Solution {
int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
public int numIslands(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
boolean[][] visited = new boolean[n][m];
int result = 0;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(!visited[i][j] && grid[i][j]=='1'){
result++;
dfs(grid,visited,i,j);
}
}
}
return result;
}
void dfs(char[][] grid,boolean[][] visited,int x,int y){
if(grid[x][y] == '0' || visited[x][y]){
return;
}
//先处理当前节点,先进行标记
visited[x][y] = true;
//然后处理四周
for(int[] d : dir){
int nextX = x+d[0];
int nextY = y+d[1];
//然后合法性判断
if(nextX<0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length){
continue;
}
//然后开始处理下一个节点
dfs(grid,visited,nextX,nextY);
}
}
}