breadth-first-search - 在矩阵中显式查找孤岛

Question

我得到一个由 0 和 1 组成的矩阵，并且必须找到由一个矩阵组成的岛屿。如果找到参考：

https://www.careercup.com/question?id=14948781

关于谁来计算岛屿的数量，但根本不知道如何调整算法以最终获得岛屿列表，给定属于它们的矩阵的单元列表。

标签： breadth-first-search

Answer 1

这个问题本质上是要求您找到无向图的连通分量。在这里，连通分量是一组被 0 包围的 1，并且该组中的任何 1 都没有连接到由 0 包围的另一个单独的 1 组。

为了解决这个问题，您可以首先对 2D 矩阵中的每个元素执行深度优先搜索 (DFS)。

1. 如果算法遇到未访问的 1，则增加岛的计数
2. 递归地对所有相邻顶点（上、下、左、右）执行 DFS
3. 跟踪访问过的 1，以便它们不再被访问（可以使用集合或通过使用布尔标志标记访问过的图中的节点来完成）
4. 在此递归 DFS 期间一旦发现 0，立即停止 DFS
5. 通过移动到 2D 矩阵中的下一个元素并重复步骤 1-4 来继续算法
6. 当您到达 2D 矩阵的末尾时，返回岛屿的数量