算法打卡：第十一章 图论part02

今日收获：岛屿数量（深搜），岛屿数量（广搜），岛屿的最大面积

1. 岛屿数量（深搜）

题目链接：99. 岛屿数量

思路：二维遍历数组，先判断当前节点是否被访问过&是否是陆地。如果满足条件则岛屿数量加1，再通过深度优先遍历将其上下左右的陆地设置为访问过。

        注意：每次传入dfs函数的节点都是符合结果收集条件的，所以不用写结束条件。也可以将判断条件（访问过/不是陆地）写入dfs的结束条件中。

方法：

import java.util.Scanner;public class Main{static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};public static void main(String[] args){// 收集输入Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();int[][] grid=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){grid[i][j]=sc.nextInt();}}int result=0;int[][] visited=new int[N][M];  // 是否访问过for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (visited[i][j]==0 && grid[i][j]==1){  // 没有访问过并且是陆地result++;visited[i][j]=1;dfs(visited,i,j,grid);  // 标记其上下左右的陆地}}}System.out.println(result);}public static void dfs(int[][] visited,int x,int y,int[][] grid){for (int i=0;i<4;i++){int nextX=x+around[i][0];int nextY=y+around[i][1];// 周围坐标在合法范围内if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){continue;  // 找下一个坐标}if (visited[nextX][nextY]==0&&grid[nextX][nextY]==1){visited[nextX][nextY]=1;dfs(visited,nextX,nextY,grid);}}}
}

2. 岛屿数量（广搜）

题目链接：99. 岛屿数量

思路：利用队列存储当前节点。当队列不为空时，从队列中取出节点作为当前遍历的节点，然后再将当前节点中符合条件的节点加入队列，同时访问位设为1

方法：

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;public class Main{static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};public static void main(String[] args){// 收集输入Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();int[][] grid=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){grid[i][j]=sc.nextInt();}}int result=0;int[][] visited=new int[N][M];  // 是否访问过for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (visited[i][j]==0 && grid[i][j]==1){  // 没有访问过并且是陆地result++;visited[i][j]=1;bfs(visited,i,j,grid);  // 标记其上下左右的陆地}}}System.out.println(result);}// 广度优先搜索public static void bfs(int[][] visited,int x,int y,int[][] grid){Queue<int[]> queue=new LinkedList<>();queue.offer(new int[]{x,y});while (!queue.isEmpty()){int curX=queue.peek()[0];int curY=queue.poll()[1];// 遍历当前节点的周围节点for (int i=0;i<4;i++){int nextX=curX+around[i][0];int nextY=curY+around[i][1];// 周围坐标在合法范围内if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){continue;  // 找下一个坐标}if (visited[nextX][nextY]==0&&grid[nextX][nextY]==1){visited[nextX][nextY]=1;queue.offer(new int[]{nextX,nextY});}}}}
}

3. 岛屿的最大面积

题目链接：100. 岛屿的最大面积

（1）深度优先遍历

思路：主函数中两层遍历的 if 判断可以当作是一个新岛屿的开始。即深度优先遍历函数返回之后，当前节点连通的岛屿节点就已经全部遍历完毕了。

方法：

import java.util.Scanner;public class Main{static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};static int current;public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();int[][] grid=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){grid[i][j]=sc.nextInt();}}int result=0;int[][] visited=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (visited[i][j]==0&&grid[i][j]==1){current=0;  // 当前节点连通岛屿的面积visited[i][j]=1;dfs(visited,i,j,grid);result=Math.max(result,current);}}}System.out.println(result);}public static void dfs(int[][] visited,int x,int y,int[][] grid){current++;for (int i=0;i<4;i++){int nextX=x+around[i][0];int nextY=y+around[i][1];if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){continue;}if (visited[nextX][nextY]==0&&grid[nextX][nextY]==1){visited[nextX][nextY]=1;dfs(visited,nextX,nextY,grid);}}}
}

 总结：递归函数中如果是求和求面积，最好把参数写在外面不容易搞混，还可以减少递归函数的参数。

（2）广度优先遍历

思路：主函数中遍历到符合条件的节点可以看作是岛屿的起点，在一次广度优先函数运行的过程中，队列添加过的元素就是这个岛屿的所有节点。因此在每次往队列中添加节点时，当前岛屿的面积就加1。

方法：

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;public class Main{static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();int[][] grid=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){grid[i][j]=sc.nextInt();}}int result=0;int[][] visited=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (visited[i][j]==0&&grid[i][j]==1){result=Math.max(result,bfs(visited,i,j,grid));}}}System.out.println(result);}public static int bfs(int[][] visited,int x,int y,int[][] grid){int current=0;Queue<int[]> queue=new LinkedList<>();visited[x][y]=1;queue.offer(new int[]{x,y});  // 当前这块岛屿的起点current++;while (!queue.isEmpty()){int currX=queue.peek()[0];int currY=queue.poll()[1];for (int i=0;i<4;i++){int nextX=currX+around[i][0];int nextY=currY+around[i][1];if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){continue;}// 满足条件加入队列，且当前岛屿面积+1if (visited[nextX][nextY]==0&&grid[nextX][nextY]==1){visited[nextX][nextY]=1;current++;queue.offer(new int[]{nextX,nextY});}}}return current;}
}