DEV Community
·
解决LeetCode的岛屿数量问题：深度优先搜索的深入探讨
💡
原文英文，约400词，阅读约需2分钟。
📝
内容提要
岛屿数量问题是深度优先搜索（DFS）在网格遍历中的经典应用。通过DFS，可以有效计算连接的“1”的组数，并直接修改输入网格以标记已访问的单元格。实现时，遍历网格，找到“1”时递增计数并进行DFS探索。时间复杂度为O(M×N)，空间复杂度为O(M×N)。
🎯
关键要点
- 岛屿数量问题是深度优先搜索（DFS）在网格遍历中的经典应用。
- 通过DFS，可以有效计算连接的'1'的组数，并直接修改输入网格以标记已访问的单元格。
- 问题理解：需要计算不同岛屿的数量，岛屿定义为连接的'1'的组。
- 实现策略：使用DFS探索连接组件，修改输入网格以跟踪已访问的单元格。
- 主要功能：遍历网格中的每个单元格，找到'1'时递增计数并开始DFS探索。
- DFS辅助函数：检查边界条件，验证当前单元格是否为岛屿的一部分，标记已访问的单元格，四个方向探索。
- 边缘情况：空网格、单行/单列网格、没有岛屿的网格、全是岛屿的网格。
- 复杂度分析：时间复杂度为O(M × N)，空间复杂度为O(M × N)。
- 优化：直接修改输入网格以标记已访问的单元格，节省空间，简化逻辑，保持连接组件属性。
❓
延伸问答
岛屿数量问题的定义是什么？
岛屿数量问题是计算连接的'1'的组数，岛屿定义为相连的'1'的集合。
如何使用深度优先搜索解决岛屿数量问题？
通过遍历网格，找到'1'时递增计数并进行DFS探索，标记已访问的单元格。
岛屿数量问题的时间和空间复杂度是多少？
时间复杂度为O(M × N)，空间复杂度为O(M × N)。
在实现岛屿数量问题时需要考虑哪些边缘情况？
需要考虑空网格、单行/单列网格、没有岛屿的网格和全是岛屿的网格。
为什么选择直接修改输入网格而不是使用单独的访问集合？
直接修改输入网格可以节省空间，简化逻辑，并保持连接组件的属性。
DFS辅助函数在岛屿数量问题中起什么作用？
DFS辅助函数检查边界条件，验证当前单元格是否为岛屿的一部分，并标记已访问的单元格。
➡️
