使用DFS查找岛屿数量

在本教程中，我们将编写一个 Python 程序来查找岛屿的数量。我们将使用各种方法来解决这个问题。这个问题可能会出现在技术面试中。首先，让我们理解以下问题陈述。

在一个二进制二维矩阵中，我们的任务是确定岛屿的数量。岛屿定义为由水平或垂直连接的相邻“1”组成的集合。例如，在下面的矩阵中，有四个不同的岛屿。我们的目标是编写 Python 程序来计算给定矩阵中此类岛屿的数量。

示例

矩阵

在深入研究解决方案之前，了解连通分量的概念很重要。这个问题是“计算无向图中的连通分量数量”的一个经典示例。

假设有一个具有多个节点和连接它们的边的图。每个连通分量将是一组相互连接的节点，但与该组外的节点不连接。因此，您可能有一组节点形成一个连通分量，而另一组节点是独立的，形成另一个连通分量。这些分量就像较大图中的孤立集群。

我们可以使用 DFS() 遍历每个分量来解决此问题。在每次 DFS() 调用中，都会访问一个分量或子图。要计算无向图中的连通分量数量，我们可以使用深度优先搜索 (DFS) 和广度优先搜索 (BFS)。每次调用 DFS 或 BFS 算法都对应于探索和标记一个连通分量。通过计算 DFS 或 BFS 调用的次数，我们确定图中连通分量的总数。这两种算法都可以有效地用于此目的。

注意 - 一组连接的 1 构成岛屿。

使用附加矩阵查找岛屿数量

附加矩阵将有助于跟踪给定矩阵中已访问的节点，并执行 DFS 以查找岛屿的总数。

以下是使用深度优先搜索 (DFS) 查找二进制二维矩阵中连通分量数量的步骤：

1. 首先，我们创建一个与给定矩阵具有相同维度的布尔矩阵 visited，并将其所有元素初始化为“false”。
2. 初始化一个变量 count 为 0，它将用于存储答案。
3. 遍历从 0 到 ROW 的行，在每一行中，遍历从 0 到 COL 的列。
4. 如果给定矩阵中的当前单元格的值为 1 且尚未访问过。则调用 DFS 函数来探索连通分量。
5. 定义两个数组，“rowNbr” = { -1, -1, -1, 0, 0, 1, 1, 1 } 和“colNbr” = { -1, 0, 1, -1, 1, -1, 0, 1 } 来表示相邻单元格。之后，我们将当前单元格标记为已访问。然后我们遍历所有八个邻居。
6. 如果邻居有效（在矩阵边界内）且尚未访问过。则递归调用邻居上的 DFS 函数。
7. 每遇到一个连通分量，count 就加 1。最后，返回 count 作为连通分量的总数。

让我们理解下面的代码片段。

示例 -

输出

Number of islands: 3

时间复杂度为 O(rows * cols)，空间复杂度为 O(rows * cols)，其中“rows”和“cols”是输入矩阵的维度。

使用深度优先搜索 (DFS) 确定岛屿数量

以下是 DFS 的步骤：

1. 首先，我们将 count 设置为 0，它将存储最终答案。
2. 遍历行（从 0 到 ROW）并在每行中，遍历列（从 0 到 COL）。
3. 如果给定矩阵中当前单元格的值为 1，则 count 加 1。
4. 调用 DFS 函数进行进一步探索。
5. 如果单元格超出了矩阵边界，或者当前单元格的值为 0，则返回。
6. 将当前单元格的值更新为 0 以将其标记为已访问。
7. 递归地将 DFS 应用于相邻单元格。
8. 将 count 作为结果返回。

让我们在代码中实现上述步骤：

示例 -

输出

Number of islands: 3

时间复杂度： O(n*m)

辅助空间： O(n*m)

结论

在本教程中，我们使用深度优先搜索 (DFS) 解决了在二进制二维矩阵中计算岛屿数量的问题。通过应用 DFS 探索连通分量，我们有效地确定了岛屿的数量。我们讨论了连通分量的概念以及它如何与问题相关。

代码示例演示了两种实现方式：一种使用附加矩阵来跟踪已访问的节点，另一种直接在原始矩阵中标记已访问的单元格。两种方法都得到了准确的结果。这种方法对于各种应用都很有用，为二进制矩阵中的岛屿计数提供了清晰有效的解决方案。