Python中的岛屿数量问题

在这个问题中，我们将得到一个只包含 1 和 0 的二维矩阵。在这个二进制矩阵中，0 被认为是水，1 被认为是岛。一个岛被认为是周围有 4 个方向的水环绕的 1 的一组。一个岛可以由通过 4 个方向连接的 1 构成（请注意，对角线上的 1 不会被考虑在同一组中）。

在这个问题中，我们将得到一个只包含 1 和 0 的二维矩阵。在这个二进制矩阵中，0 被认为是水，1 被认为是岛。一个岛被认为是周围有 4 个方向的水环绕的 1 的一组。一个岛可以由通过 4 个方向连接的 1 构成（请注意，对角线上的 1 不会被考虑在同一组中）。

并且整个矩阵假定被水环绕。

让我们通过一个例子来理解这一点。

输入： 矩阵 =

[[1, 1, 1, 0, 0],

1, 1, 0, 1, 1],

[1, 0, 0, 1, 0],

[0, 1, 0, 0, 0]]

输出 3

在这个 2D 矩阵中，有 3 组 1。第一组位于左上角列，从行 0 到 2，从列 0 到 2。第二组位于行 1 到 2，从列 3 到 4。第三组是位于索引 (2, 2) 的孤立的 1。请注意，最后一个元素不能被视为第 1 组的一部分，因为它仅通过对角线连接到第 1 组的元素。

我们将使用图数据结构的连通分量概念来解决这个问题。为了解决这个问题，首先我们需要理解图中的连通分量是什么。图是一种数据结构，其中存在一定数量的顶点，通过一定数量的边连接。然而，一个图可以分成几个分量，但仍然被认为是一个图。当图中的任何一个簇的节点不与任何其他簇的节点连接时，就会发生这种情况。下面是一个图的连通分量的示例

在上面的例子中，一个图有两个分量。

一个所有顶点都连接并且可以在一次遍历中到达所有顶点的图，被称为具有单个分量。这种类型的图称为强连通图。然而，如果我们需要多次遍历迭代才能到达图的所有顶点，那么该图就被称为具有多个分量。

可以使用深度优先搜索 (DFS) 和广度优先搜索 (BFS) 算法遍历图。我们将使用这两种遍历来解决这个问题。

解决问题的核心思想是定义两个函数，一个用于遍历，另一个用于计算遍历次数。在第二个函数中，我们将创建一个与给定矩阵大小相同的矩阵，并在所有元素的位置上填充 False。现在，我们将运行一个嵌套的 for 循环遍历数组的每个元素，每当遇到一个在给定矩阵中为 1 并且在 visited 数组中标记为 False 的元素时，简而言之，就是未访问的元素，我们将调用遍历函数。在此循环中，我们必须计算调用遍历函数的次数。在遍历函数中，每个访问过的矩阵单元格将在 visited 矩阵的相应索引处被标记为 True。遍历函数被调用的次数就是我们的解决方案。这个数字代表了在这个问题中未连接分量或岛屿的数量。

方法 - 1

在此方法中，我们将使用 DFS 遍历来遍历矩阵。思路与上述相同。我们将创建一个矩阵来跟踪已访问的顶点。

让我们来看一下这个问题的算法

• 第一步是初始化一个与给定矩阵大小相同的 visited[] 矩阵。这个 visited[] 矩阵的每个元素都将设置为 False。
• 然后，我们将初始化岛屿计数，count = 0。
• 现在，我们将启动一个 for 循环，该循环将遍历矩阵的所有行；在此循环内，将有另一个循环遍历矩阵的所有列。
  • 在内部循环中，我们将检查当前元素在给定矩阵中是否为 1，并且在 visited[] 矩阵中是否标记为 False。
  • 如果是，那么我们将 count 加 1。
  • 此外，我们将调用遍历函数，并将当前元素作为源元素传递给该函数。
  • DFS 遍历函数将首先将源元素标记为 True，在 visited[] 矩阵中。
  • 然后，我们将循环遍历当前源元素的相邻元素。相邻元素是源元素 4 个方向上的元素。为了组织代码，我们将创建两个数组，row = [-1, 0, 0, 1] 和 column = [0, -1, 1, 0]。它们将确保为源元素的所有相邻元素调用该函数。
• 假设当前相邻元素有效，即在矩阵的边界内，并且在给定矩阵中被标记为 1。在这种情况下，我们将递归地为相邻元素调用 DFS 函数。
• 当所有遍历都完成后，我们将返回岛屿的计数，即 count。

以下是使用 DFS 遍历的这种方法的 Python 代码。

代码

输出

The number of islands in the given matrix is:
3

时间复杂度：我们在 countIslands() 函数中访问矩阵的每个单元格。因此，时间复杂度是非线性的，即 O(r x c)，其中 r 是给定矩阵的总行数，c 是列数。

辅助空间：我们创建了一个矩阵来存储已访问的单元格；因此，空间复杂度为 O(r x c)。

上述问题可以修改为使对角线元素也构成一个岛屿。在这种情况下，我们需要在对角线元素上也调用递归 DFS 遍历函数，如果对角线元素有效的话。我们将把 DFS 遍历的 row[] 和 column[] 矩阵中的索引包含进去，这样每个特定元素将检查 8 个索引而不是 4 个。

以下是更新问题的代码。

代码

输出

The number of islands in the given matrix is:
3

空间优化

在上述算法中，我们创建了一个单独的矩阵来存储已访问的节点。我们可以通过就地解决此问题来优化空间复杂度，这样我们就不需要额外的 O(r * c) 空间。

以下是空间优化的代码。

代码

输出

The number of islands in the given matrix is:
3

方法 - 2

在此方法中，我们将使用 BFS 算法。邻居被认为是单元格的非对角线元素。因此，总共有 4 个邻居。因此，在此问题中，我们将不对所有相邻单元格使用 BFS；相反，我们将对 4 个相邻单元格使用 BFS。我们将跟踪已访问的单元格，以确保我们不会再次访问它们。

以下是此问题的算法方法

• 我们将初始化一个与给定矩阵大小相同的二维矩阵。我们将此矩阵的所有值设置为 False。此矩阵将跟踪已访问的单元格。
• 现在，我们将遍历给定矩阵，对于每个未访问且在给定矩阵中标记为岛屿的单元格，我们将执行 BFS 遍历函数。
• 在 BFS 遍历函数中，我们将创建一个队列数据结构，并将源节点放入其中。此外，我们将源节点在 visited 矩阵中标记为已访问。
• 然后，我们将启动一个 while 循环，直到队列为空。
  • 在循环中，我们将出队队列中的节点；然后，我们将该节点的有效相邻节点添加到队列中，并将这些在给定矩阵中标记为岛屿的相邻节点标记为已访问。
• 当前源代码的 BFS 完成后，我们将岛屿计数加 1。
• BFS 将为每个有效的未访问单元格调用。
• 最后，我们将返回总岛屿计数。

代码

输出

Number of islands in the given matrix is: 5

时间复杂度： O(ROW * COL)，其中 ROW 是矩阵的行数，COL 是列数。

辅助空间： O(ROW * COL)，因为有 visited 数组。