代码随想录算法训练营四十四天|图论part02

岛屿问题（一）岛屿数量：深搜版

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

3

提示信息

根据测试案例中所展示，岛屿数量共有 3 个，所以输出 3。

数据范围：

1 <= N, M <= 50

代码如下：

import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        int[][] graph=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                graph[i][j]=in.nextInt();
            }
        }
        int ans=0;
        boolean[][] visited=new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(visited[i][j]==false&&graph[i][j]==1){
                    ans++;
                    visited[i][j]=true;
                    dfs(graph,visited,i,j);
                }
            }
        }
        System.out.println(ans);
    }
    public static final int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};
    public static void dfs(int[][] graph,boolean[][] visited,int x,int y){
        for(int i=0;i<4;i++){
            int nextx=x+dir[i][0];
            int nexty=y+dir[i][1];
            if(nextx<0||nexty<0||nextx>=graph.length||nexty>=graph[0].length)continue;
            if(visited[nextx][nexty]==false&&graph[nextx][nexty]==1){
                visited[nextx][nexty]=true;
                dfs(graph,visited,nextx,nexty);
            }
        }
    }
}

岛屿问题（二）岛屿数量：广搜版

代码如下：

import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        int[][] graph=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                graph[i][j]=in.nextInt();
            }
        }
        int ans=0;
        boolean[][] visited=new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(visited[i][j]==false&&graph[i][j]==1){
                    ans++;
                    bfs(graph,visited,i,j);
                }
            }
        }
        System.out.println(ans);
    }
    private static final int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};
    public static void bfs(int[][] graph,boolean[][] visited,int x,int y){
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{x,y});
        visited[x][y]=true;
        while(!q.isEmpty()){
            int[] cur=q.poll();
            int curx=cur[0];
            int cury=cur[1];
            for(int i=0;i<4;i++){
                int nextx=curx+dir[i][0];
                int nexty=cury+dir[i][1];
                if(nextx<0||nexty<0||nextx>=graph.length||nexty>=graph[0].length)continue;
                if(visited[nextx][nexty]==false&&graph[nextx][nexty]==1){
                    visited[nextx][nexty]=true;
                    q.offer(new int[]{nextx,nexty});
                }
            }
        }
    }
}

岛屿问题（三）岛屿的最大面积

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

4

提示信息

样例输入中，岛屿的最大面积为 4。

数据范围：

1 <= M, N <= 50。

代码如下（深搜版）：

import java.util.*;
 
public class Main {
    private static int Max = 0;
    private static int ans=0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = in.nextInt();
            }
        }
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j] == false && graph[i][j] == 1) {
                    ans=1;
                    visited[i][j] = true;
                    dfs(graph, visited, i, j);
                    Max=Math.max(Max,ans);
                }
            }
        }
        System.out.println(Max);
    }
 
    private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public static void dfs(int[][] graph, boolean[][] visited, int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nexty < 0 || nextx >= graph.length || nexty >= graph[0].length)
                continue;
            if (visited[nextx][nexty] == false && graph[nextx][nexty] == 1) {
                visited[nextx][nexty] = true;
                ans++;
                dfs(graph, visited, nextx, nexty);
            }
        }
    }
}

广搜版：

import java.util.*;
 
public class Main{
    private static int ans=0;
    private static int Max=0;
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        int[][] graph=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                graph[i][j]=in.nextInt();
            }
        }
        boolean[][] visited=new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(visited[i][j]==false&&graph[i][j]==1){
                    ans=1;
                    bfs(graph,visited,i,j);
                    Max=Math.max(Max,ans);
                }
            }
        }
        System.out.println(Max);
    }
    private static final int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};
    public static void bfs(int[][] graph,boolean[][] visited,int x,int y){
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{x,y});
        visited[x][y]=true;
        while(!q.isEmpty()){
            int[] cur=q.poll();
            int curx=cur[0];
            int cury=cur[1];
            for(int i=0;i<4;i++){
                int nextx=curx+dir[i][0];
                int nexty=cury+dir[i][1];
                if(nextx<0||nexty<0||nextx>=graph.length||nexty>=graph[0].length)continue;
                if(visited[nextx][nexty]==false&&graph[nextx][nexty]==1){
                    ans++;
                    visited[nextx][nexty]=true;
                    q.offer(new int[]{nextx,nexty});
                }
            }
        }
    } 
}

没什么好说的，都是模板题。