Java 中查找岛屿的数量

17 Mar 2025 | 6 分钟阅读

查找岛屿数量问题是标准问题，通常在顶尖公司的编码轮面试中被问到。这个问题基于图论。在图论中，我们查找连通分量的数量。在这个问题中，我们也需要做同样的事情。因此，在本节中，我们将讨论岛屿问题陈述、算法以及查找岛屿数量的 Java 程序。

问题陈述

在这个问题中，岛屿只不过是布尔一维、二维或多维 (n 维) 数组中相连的“1”的集合。在这个问题中，我们需要查找布尔矩阵中岛屿（“1”的集合）的数量。“1”表示陆地。

陈述可以重写如下。

给定一个布尔二维矩阵，其中“1”表示陆地，“0”表示水。在这个矩阵中，我们需要计算岛屿的数量。岛屿是环绕着水并且由水平或垂直相邻陆地连接而形成的区域。假设网格的所有四个边缘都环绕着水。下图描绘了这一点。

在上图中，用绿色突出显示的方块（“1”）表示陆地，用黄色突出显示的方块（“0”）表示水。上述矩阵有五个岛屿。

上述问题与无向图中的连通分量有关。因此，我们首先将理解什么是连通分量。

连通分量

连通分量是指图中的每对节点都可以通过路径相互连接，并且不与子图之外的任何其他顶点连接。例如，考虑以下图。

示例

考虑以下矩阵。

在上图中，只有一个相连的“1”的集合。因此，它表示只有一个岛屿。

问题解决方案

这个问题有许多解决方案。它可以是使用 DFS 或 BFS 来解决。在本节中，我们将使用递归和非递归的 DFS 方法来解决这个问题。

使用深度优先搜索 (DFS)

在这种方法中，我们将逐一遍历矩阵中的所有陆地（“1”）。如果我们发现任何未遍历或尚未访问过的陆地，这意味着我们找到了一个新的岛屿。一旦我们访问了一个岛屿，我们将岛屿数量加 1。使用 DFS 或 BFS，我们将所有相连的陆地标记为已访问。

算法

定义一个布尔数组，并将所有值设置为 false。
定义一个变量ans并将其初始化为 0。我们将在此变量中存储最终答案。
遍历网格的每个元素。
检查它是否是陆地（“1”），如果不是，则将变量ans加一。
之后，为此元素启动 DFS 或 BFS 遍历。

查找岛屿数量的 Java 程序

递归方法

在以下 Java 程序中，我们维护了一个名为visited的数组。它跟踪我们已经访问过的陆地。定义并初始化一个变量answer，它存储岛屿的数量。

让我们在 Java 程序中实现上述方法。

NumberOfIslands.java

public class NumberOfIslands
{
//function that find the number of islands     
public int findIslands(char[][] matrix) 
{
//finds and stores the length of the matrix or grid    
int h = matrix.length;
if (h == 0)
//if matrix has no elements, returns 0
return 0;
int l = matrix[0].length;
//variable to store result
int result = 0;
//loop iterates over rows
for (int i = 0; i < h; i++) 
{
//loop iterates over columns    
for (int j = 0; j < l; j++) 
{
//
if (matrix[i][j] == '1') 
{
//if the above condition returns true, calls the dfs() function and increments the result
dfs(matrix, i,  j);
result++;
}
}
}
return result;
}
//function performs the depth first search over the matrix
public void dfs(char[][] matrix, int row, int col) 
{
int H = matrix.length;
int L = matrix[0].length;
//returns true if any of the condition returns true
if (row < 0 || col < 0 || row >= H || col >= L || matrix[row][col] != '1')
return;
//marking element as visited
matrix[row][col] = '0'; 
//moves in right direction
dfs(matrix, row+ 1, col); 
//moves in left direction
dfs(matrix, row- 1, col); 
//moves in downward direction
dfs(matrix, row, col + 1); 
//moves in upward direction
dfs(matrix, row, col - 1); 
}
//driver code
public static void main(String args[]) 
{
//creating an instance of teh class    
NumberOfIslands noi = new NumberOfIslands();
//grid in which we have to find number of islands
char[][] islandGrid = new char[][] 
{
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}};
//prints the result
System.out.println("Number of Islands: " + noi.findIslands(islandGrid));
}
}

输出

Number of Islands: 3

使用非递归方法

NumberOfIslands.java

import java.util.Stack;	
public class NumberOfIslands 
{
//function that find the number of islands         
public int findIslands(char[][] matrix) 
{
//finds and stores the number of rows
int h = matrix.length;
if (h == 0)
//if matrix has no elements, returns 0
return 0;
//finds and store the number of columns in row 0
int l = matrix[0].length;
//stores the number of islands
int result = 0;
//returns true if the same number of columns as the first row
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
//loop for rows
for (int i = 0; i < h; i++) 
{
//loop for columns    
for (int j = 0; j < l; j++) 
{
//set element to false    
visited[i][j] = false;
}
}
//creating stack
Stack<String> stack = new Stack<>();
for (int i = 0; i < h; i++) 
{
for (int j = 0; j < l; j++) 
{
//returns true if both condtions returns true    
if (!visited[i][j] && matrix[i][j] == '1') 
{
//if the above condtion returns true, push the i-th row and the j-th column to the stack    
stack.push(i + "," + j);
//calling the dfs() function
dfs(stack, matrix, visited);
result++;
}
}
}
return result;
}
//function performs the depth first search over the matrix
public void dfs(Stack<String> stack, char[][] matrix, boolean[][] visited) 
{
int H = matrix.length;
int L = matrix[0].length;	
while (stack.empty() == false) 
{
String x = stack.pop();
//casting rows and columns
int row = Integer.parseInt(x.split(",")[0]);
int col = Integer.parseInt(x.split(",")[1]);
if(row<0 || col<0 || row>=H || col>=L || visited[row][col] || matrix[row][col]!='1')
continue;
//marking element as visited
visited[row][col]=true;
//moves in left direction
stack.push(row + "," + (col-1));
//moves in right direction
stack.push(row + "," + (col+1));
//moves in upward direction
stack.push((row-1) + "," + col);
//moves in downward direction
stack.push((row+1) + "," + col); 
} //end of while loop
}
public static void main(String args[]) 
{
//creating an instance of the class    
NumberOfIslands noi = new NumberOfIslands();
//grid in which we have to find number of islands
char[][] island= new char[][] 
{
                {'1', '1', '0', '0', '1'},
                {'1', '0', '0', '1', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}};
//prints the result
System.out.println("Number of Islands: " + noi.findIslands(island));
}
}

输出

Number of Islands: 5

复杂度

对于上述问题，时间复杂度为O(n*m)，因为我们至少访问了网格的每个元素一次。其中，n 是行数，m 是列数。

上述方法空间复杂度为O(n*m)，因为我们使用了一个二维数组来存储陆地是否已被访问。

下一主题Java 中的平衡素数

Java 中查找岛屿的数量

问题陈述

连通分量

问题解决方案

使用深度优先搜索 (DFS)

查找岛屿数量的 Java 程序

递归方法

使用非递归方法

复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中查找岛屿的数量

问题陈述

连通分量

问题解决方案

使用深度优先搜索 (DFS)

查找岛屿数量的 Java 程序

递归方法

使用非递归方法

复杂度

相关帖子

Java Constant

Java Stream 的不同字符计数

Longest Common Subsequence

如何使用递归在 Java 中反转字符串

Java 中使用 == 和 .equals() 方法比较 String 的区别

Multiply Two Polynomials in Java

Getter and Setter Method in Java Example

Stern-Brocot Sequence in Java

Java 中的排列程序

Twin Prime Numbers

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器