你好！今天我们将一起深入探讨一道在算法面试中极具代表性的经典题目——岛屿数量。这不仅是一道考验我们代码控制力的题目，更是理解图论、深度优先搜索（DFS）以及并查集等核心计算机科学概念的绝佳入口。如果你曾经对如何在二维网格中进行“漫水填充”感到困惑，或者想知道如何优雅地处理边界条件，那么这篇文章正是为你准备的。
我们将一步步拆解问题，从最直观的思路入手，逐步过渡到最优解法。准备好你的咖啡，让我们开始这场算法探索之旅吧。
问题描述与核心概念
想象一下，你正在通过卫星俯瞰地球的表面。我们将地图抽象为一个二维的网格地图 INLINECODE7b8b5da4，大小为 INLINECODE9d041ecf。在这个网格中：
-
1代表陆地：这是我们关注的重点。 -
0代表水域：这是背景。
我们的任务是计算出地图中岛屿的数量。在这里，“岛屿”有着非常具体的数学定义：它是指被水域（INLINECODE1e328ae6）包围的陆地（INLINECODE1ee33655）集合，并且集合内的陆地必须通过水平或垂直方向（通常是上、下、左、右四个方向，不包括对角线）相邻连接。
为了简化问题，我们可以假设网格的四个外部边界均被水包围。这意味着我们不需要处理“飞出地图边缘”的特殊情况，因为边缘以外的区域自动视为水域。
#### 为什么这道题很重要？
在这道题中，我们本质上是在处理连通性问题。网格中的每一个单元格都可以看作是图中的一个节点，而相邻的陆地单元格之间则存在边。寻找岛屿的数量，实际上就是在寻找图中连通分量的数量。掌握了这个模式，你将能够轻松解决诸如“最大岛屿面积”、“闭合岛屿数量”等更为复杂的变体问题。
示例分析与思路拆解
让我们通过具体的例子来理解题目的要求和预期的行为。
#### 示例 1：最小单位
输入：
grid = {{0, 1},
{1, 0}}
输出：
2
解释：
我们将网格可视化如下：
0 1
1 0
在这个 2×2 的网格中，位置 INLINECODE1b7eb19e 的 INLINECODE74489dbe 和位置 INLINECODE30744921 的 INLINECODE59a9f74d 虽然都是陆地，但它们是对角线关系，而非水平或垂直相邻。因此，它们各自独立，被水域隔开。我们可以清楚地看到这里有两个岛屿。
#### 示例 2：连通与非连通
输入：
grid = {{0, 1, 1, 1, 0, 0, 0},
{0, 0, 1, 1, 0, 1, 0}}
输出：
2
解释：
可视化后的地图：
0 1 1 1 0 0 0
0 0 1 1 0 1 0
让我们来分析一下这个结果：
- 左上角的岛屿：在第 0 行，我们有连续的三个 INLINECODE93e86a93（索引 1, 2, 3）。在第 1 行，索引 2 和 3 也是 INLINECODE54d96148。注意，第 0 行的 INLINECODE78ce048a 和第 1 行的 INLINECODE2e817dd5 是垂直相连的。因此，这些所有的
1实际上连成了一片巨大的陆地。 - 右侧的孤岛：在第 1 行的索引 5 处有一个 INLINECODE93259de1。它的上下左右（INLINECODE769e5f24, INLINECODE5a868e5f, INLINECODE154285ea, INLINECODE70689cba）要么是出界，要么是 INLINECODE95caa41d。因此，它独立成岛。
所以，尽管网格中有多个 1，但它们最终形成了两个独立的连通区域。
算法思路：如何“消灭”岛屿
解决这个问题最直观的方法是遍历整个网格。当我们遇到一个值为 1 的陆地单元格时，意味着我们发现了一个新的岛屿。此时，我们应该将计数器加 1。
但是，仅仅计数是不够的。如果我们继续遍历，遇到这个岛屿的其他部分时，可能会重复计数。为了避免这种情况，我们需要一种机制来标记这块陆地已经被访问过了。这就是算法的核心：
> 当我们发现一块新陆地时，计数 +1，然后通过搜索算法（DFS 或 BFS）将与其相连的所有陆地都“标记”为已访问（例如改为 0 或标记为 -1）。 这样，后续的遍历就会跳过这些区域。
方法一：深度优先搜索 (DFS)
DFS 是解决这类问题最常用且代码最简洁的方法。它的思想像是一个执着的探险家，一旦发现新大陆（1），就立刻深入下去，把这块大陆上每一寸土地都踩一遍，直到遇到水才回头。
#### 核心代码实现
为了方便你直接复制和调试，我准备了完整的函数实现。请注意其中的注释，它们解释了每一步的关键逻辑。
#include
#include
using namespace std;
class Solution {
public:
// 主函数：计算岛屿数量
int numIslands(vector<vector>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int n = grid.size(); // 行数
int m = grid[0].size(); // 列数
int count = 0; // 岛屿计数器
// 遍历整个网格的每一个单元格
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
// 如果发现陆地 ('1')
if (grid[i][j] == '1') {
count++; // 发现新岛屿，计数加 1
// 关键步骤：通过 DFS 将该岛屿淹没（标记为 '0'），防止重复计数
dfs(grid, i, j);
}
}
}
return count;
}
private:
// 私有辅助函数：深度优先搜索
// i, j 代表当前搜索的坐标
void dfs(vector<vector>& grid, int i, int j) {
int n = grid.size();
int m = grid[0].size();
// 边界条件检查：
// 1. 坐标越界
// 2. 当前位置是水域 (‘0‘)，不需要继续搜索
if (i = n || j = m || grid[i][j] == ‘0‘) {
return;
}
// 标记当前陆地为已访问（这里直接将其改为 ‘0‘，即“沉岛”操作）
grid[i][j] = ‘0‘;
// 递归调用：向上下左右四个方向继续搜索
dfs(grid, i + 1, j); // 下
dfs(grid, i - 1, j); // 上
dfs(grid, i, j + 1); // 右
dfs(grid, i, j - 1); // 左
}
};
#### 代码深度解析
- “沉岛”技巧：请注意 INLINECODE87dce085 这一行。这是一个非常实用的技巧。与其创建一个额外的 INLINECODEc74ba400 数组来记录哪些点去过，不如直接把去过的陆地变成水。这样既节省了空间，又省去了维护额外数组的麻烦。
- 递归的基准情形：在
dfs函数的开头，我们首先检查了边界和当前值。这是所有递归函数的“安全阀”。如果没有它，程序将无限递归直到栈溢出。
方法二：广度优先搜索 (BFS)
除了 DFS，我们还可以使用 BFS。DFS 是一条路走到黑，而 BFS 则是层层推进。如果你担心在极大网格上使用递归会导致栈溢出（Stack Overflow），那么使用队列实现的迭代版 BFS 会是更安全的选择。
#### 核心代码实现
这里我们使用标准库中的 queue 来辅助实现。
#include
#include
using namespace std;
class Solution {
public:
// 辅助方向数组：简化代码，避免写四次相同的逻辑
// 对应 上, 下, 左, 右
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
int numIslands(vector<vector>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int n = grid.size();
int m = grid[0].size();
int islands = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == '1') {
islands++;
grid[i][j] = '0'; // 标记入口
queue<pair> q;
q.push({i, j}); // 将当前陆地放入队列
// 开始广度优先遍历
while (!q.empty()) {
auto front = q.front();
q.pop();
int x = front.first;
int y = front.second;
// 检查四个方向
for (int k = 0; k = 0 && nx = 0 && ny < m && grid[nx][ny] == '1') {
grid[nx][ny] = '0'; // 标记为已访问
q.push({nx, ny}); // 加入队列等待后续处理
}
}
}
}
}
}
return islands;
}
};
#### 代码深度解析
- 方向数组 (INLINECODE7a74d34d, INLINECODE4d68d684)：在 BFS 版本中，我引入了 INLINECODE5a3da2b6 和 INLINECODE8af0ae35 数组。这是一种极佳的代码优化实践。它将四个方向的遍历逻辑合并为一个循环，极大地减少了代码冗余，也降低了写错坐标的可能性。
- 队列的作用：队列保证了我们是按层级进行访问的。虽然在这个特定问题中，DFS 和 BFS 的最终结果（岛屿数量）是一样的，但在寻找“最短路径”相关的问题中，BFS 的特性则是至关重要的。
方法三：并查集 —— 进阶思维
如果你在面试中写出了 DFS，面试官可能会紧接着问：“有没有非递归、且不使用栈/队列的方法？” 这时候，并查集 就是你展示深厚功底的杀手锏。
并查集的核心思想是：“连通的元素属于同一个集合”。
- 初始化时，所有的
1都是独立的岛屿。 - 我们遍历网格，只要发现两个相邻的
1，就把它们合并（Union）成一个集合。 - 最后，我们统计还剩下多少个独立的集合根节点，就是岛屿的数量。
这种方法实现起来稍微复杂一些，但在处理动态连通性问题时具有天然优势。
性能分析与复杂度
无论你选择 DFS 还是 BFS，它们的时空复杂度都是一致的。
时间复杂度：O(N M)
在最坏的情况下，我们需要访问网格中的每一个单元格。即使有回溯或跳跃操作，每个单元格最多被访问两次（一次在主循环，一次在搜索过程中）。因此，时间复杂度与网格的大小成线性正比。
空间复杂度：O(N M)
主要消耗在于搜索过程中的存储空间。
DFS：最坏情况是网格全是陆地，递归调用的深度会达到 NM，导致调用栈空间占用 O(N*M)。这也是为什么在大数据量下推荐使用 BFS 的原因。
BFS：同理，队列中最多可能存储 NM 个节点。
实际应用与最佳实践
在实际开发中，这种“漫水填充”算法有着广泛的应用，远不止于计算岛屿数量：
- 图像处理：你可以用这个算法来识别图片中的特定颜色区域（例如，“魔棒”工具）。如果你想抠出一张照片中蓝天白云的部分，本质上就是在进行连通区域分析。
- 游戏开发：在自动生成地图时，检测是否有无法到达的封闭区域；或者在消除类游戏中检测是否有连续的可消除方块。
最佳实践提示：
- 递归深度限制：如果你使用 DFS 且测试用例网格非常大（比如 500×500 全是 1），Python 或 Java 可能会报 INLINECODE511ee63b 或 INLINECODE4568c796。解决方案：手动使用栈来实现 DFS，或者直接改用 BFS。
- 原地修改：如果允许修改输入数组，尽量使用“原地标记法”（将 INLINECODEe9c40341 改为 INLINECODE6e8ce521）。如果面试官要求不能修改输入，那你必须创建一个
visited[n][m]的布尔矩阵，这会增加 O(NM) 的空间开销。
常见错误与解决方案
在编写这道题时，新手（甚至老手）经常踩坑，这里列出几个最常见的“陷阱”：
- 重复计数：忘记在找到新岛屿后进行“沉岛”操作或标记访问。这会导致同一个连通分量被重复计算多次。
- 边界检查错误：在递归或循环中，错误地编写了 INLINECODEd6b10625 或 INLINECODE5cd0e060，导致数组越界。记住，有效索引是
[0, n-1]。 - 对角线陷阱：题目通常明确说明不包括对角线方向。如果你错误地检查了
(i-1, j-1)等位置，可能会导致本应分开的岛屿被合并。
总结
在这篇文章中，我们从最基本的网格遍历出发，深入探讨了如何使用深度优先搜索 (DFS) 和 广度优先搜索 (BFS) 来解决岛屿数量问题。我们还简要触及了并查集这一高级数据结构。
解决这个问题的关键在于思维方式的转变：将二维网格看作图，将岛屿看作连通分量。掌握了这一点，你不仅能解决“岛屿数量”，还能触类旁通，解决一整类基于网格搜索的算法难题。
下一步行动
既然你已经掌握了 DFS 和 BFS 的精髓，我建议你尝试以下挑战来巩固你的技能：
- LeetCode 695: Max Area of Island：这道题要求我们不仅要数岛屿，还要找出面积最大的那个岛屿。只需要在 DFS 中加一个计数器即可实现。
- LeetCode 130: Surrounded Regions：尝试反转被 ‘X‘ 包围的 ‘O‘。这考察的是 BFS/DFS 的逆向思维和边界处理。
希望这篇文章对你有所帮助。编码愉快！