算法打卡：第十一章 图论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;
}
// 满足条件加入队列，且当前岛屿面积+1
if (visited[nextX][nextY]==0&&grid[nextX][nextY]==1){
visited[nextX][nextY]=1;
current++;
queue.offer(new int[]{nextX,nextY});
}
}
}
return current;
}
}