C++ 程序使用 DFS 查找岛屿数量

一个典型的算法问题，经常出现在图论和图像处理中，是需要一个 C++ 程序使用深度优先搜索 (DFS)来计算岛屿的数量。在本文中，我们将讨论使用 DFS 查找岛屿数量的 C++ 程序。

示例

让我们举一个例子来演示如何使用 C++ 中的 DFS 查找岛屿数量。

输出

Number of islands: 3

说明

1. Solution 类

在这个例子中，Solution 类是确定这个类中包含多少岛屿的答案。numIslands 和 dfs 是这个类中存在的两个主要方法。

2. numIslands 方法

此方法用于定义二进制矩阵中的岛屿数量。它接受一个由 2D 向量网格表示的二进制矩阵作为参数。它初始化并设置为 0 一个名为 num 的整型变量，用于跟踪岛屿的种类。

3. 边界情况检查

检查输入网格的边界情况，即网格为空或包含空行。如果其中任何一个条件为 true，则返回 0，表示没有岛屿。

4. 网格迭代

在该方法中，使用嵌套循环遍历整个二进制矩阵。内部循环和外部循环都遍历列和行。

5. 岛屿的 DFS

在矩阵中，在坐标 (i, j) 处存在 “1”（表示陆地）表示新岛屿的开始。之后，该方法调用 dfs 方法进行深度优先搜索，以将整个岛屿标记为已访问。它在标记岛屿后增加 num 变量以计数该岛屿。

6. dfs 方法

• 整个岛屿将使用此递归 DFS 方法标记为已访问。
• 当前行和列坐标是输入参数，以及二进制矩阵网格。
• 基本情况：它验证基本情况，以防止移出边界或停在已经访问过 ('0') 的单元格或水域。
• 如果任何这些基本条件为真，它只是返回。
• 添加访问标记
• 将 “1” 更改为 “0”，表示当前单元格已访问。
• 递归：它反复向四个方向（上、下、左、右）探索相邻单元格，以表明整个岛屿已被访问。

7. main 函数

主函数包含示例二进制矩阵 (grid) 的定义。接下来，生成 Solution 类实例。使用 numIslands 技术计算岛屿数量。之后，输出是岛屿的总数。

8. 输出

该程序打印在二进制矩阵中发现的岛屿数量。

复杂度

• 通常，此程序的时间复杂度为 O(rows * cols)，其中 “rows” 表示矩阵的行数，“cols” 表示矩阵的列数。这是因为每个单元格只访问一次。
• 递归 DFS 实现的空间复杂度为 O(1)，因为没有使用额外的额外数据结构。但是，函数调用堆栈可能会增加大型输入所需的存储量。

结论

总之，使用 DFS 计算岛屿数量的 C++ 程序是用于在二进制矩阵中定位“1”的连接簇的有用工具。它使用 DFS 算法有效地遍历矩阵并计算岛屿数量。