LeetCode 200. 岛屿数量(C++)：深度优先与广度优先的实战对比

1. 岛屿数量问题解析第一次看到LeetCode 200题岛屿数量时很多人会感到困惑这个看似简单的矩阵遍历问题为什么会被标记为中等难度让我用一个生活中的例子来解释想象你面前有一张卫星地图上面蓝色代表海洋绿色代表陆地。你的任务是统计这张地图上有多少个独立的岛屿。这里的独立很关键 - 任何相连的陆地上下左右相邻都属于同一个岛屿。在实际解题中我们需要解决三个核心问题如何判断两个陆地格子属于同一个岛屿如何确保不会重复统计同一个岛屿如何高效地遍历整个地图我刚开始做这道题时犯过一个典型错误直接遍历矩阵每遇到一个1就计数加一。结果发现严重高估了岛屿数量因为没有考虑相邻陆地属于同一岛屿的情况。后来才明白必须把相连的所有1都标记为已访问才能准确统计。2. 深度优先搜索(DFS)实现详解2.1 DFS核心思想深度优先搜索就像探险家登岛后的行为从登陆点开始一直往一个方向走到底直到无路可走再回溯。这种一条路走到黑的特点非常适合探索岛屿的边界。在代码实现上DFS通常使用递归这带来两个优势代码简洁直观与算法思想高度吻合系统栈自动处理回溯无需额外数据结构但要注意递归深度问题。我曾经在一个100x100的全1矩阵上测试直接爆栈。这说明DFS在极端情况下存在隐患。2.2 完整DFS代码实现class Solution { public: void dfs(vectorvectorchar grid, int i, int j) { // 越界检查或非陆地则返回 if(i 0 || i grid.size() || j 0 || j grid[0].size() || grid[i][j] ! 1) return; grid[i][j] 0; // 标记为已访问 // 四个方向递归探索 dfs(grid, i1, j); dfs(grid, i-1, j); dfs(grid, i, j1); dfs(grid, i, j-1); } int numIslands(vectorvectorchar grid) { if(grid.empty()) return 0; int count 0; for(int i 0; i grid.size(); i) { for(int j 0; j grid[0].size(); j) { if(grid[i][j] 1) { dfs(grid, i, j); count; } } } return count; } };这个版本比原始代码更健壮增加了边界检查。实际测试中处理100x100矩阵约需8ms空间复杂度O(M×N)最坏情况下递归深度。3. 广度优先搜索(BFS)实现剖析3.1 BFS算法特点广度优先搜索采用层层推进的策略就像在岛上以登陆点为中心一圈圈向外探索。这种特性使BFS能更均匀地探索整个岛屿避免DFS可能出现的一条路走到黑的情况。BFS特别适合寻找最短路径这道题不需要避免递归深度过大需要均匀探索的场景3.2 BFS实现细节class Solution { public: int numIslands(vectorvectorchar grid) { if(grid.empty()) return 0; int rows grid.size(), cols grid[0].size(); int count 0; queuepairint,int q; for(int i 0; i rows; i) { for(int j 0; j cols; j) { if(grid[i][j] 1) { count; q.push({i,j}); grid[i][j] 0; while(!q.empty()) { auto [x,y] q.front(); q.pop(); // 检查四个方向 if(x 0 grid[x-1][y] 1) { q.push({x-1,y}); grid[x-1][y] 0; } if(x rows-1 grid[x1][y] 1) { q.push({x1,y}); grid[x1][y] 0; } if(y 0 grid[x][y-1] 1) { q.push({x,y-1}); grid[x][y-1] 0; } if(y cols-1 grid[x][y1] 1) { q.push({x,y1}); grid[x][y1] 0; } } } } } return count; } };关键点必须在入队时立即标记为已访问而不是出队时处理。我曾在出队时标记结果导致某些节点被重复入队最终超时。4. DFS与BFS的实战对比4.1 性能基准测试我在LeetCode测试平台上对两种方法进行了对比单位ms测试用例DFS时间BFS时间100x100全1812稀疏岛屿45蛇形岛屿67DFS在大多数情况下稍快因为递归调用开销小于队列操作缓存局部性更好连续内存访问但BFS在极端情况下如非常深的岛屿更稳定不会爆栈。4.2 内存使用对比DFS的内存消耗取决于递归深度最坏O(M×N)BFS的队列在最坏情况下也需要O(min(M,N))空间。实际测试中方法平均内存使用DFS12MBBFS14MB4.3 适用场景建议根据我的项目经验小规模数据或岛屿形状简单 → DFS更简洁大规模数据或需要稳定性 → BFS更可靠并行计算场景 → BFS更容易并行化5. 并查集解法揭秘5.1 并查集核心思想并查集(Union-Find)是解决连通性问题的利器。它将每个陆地视为独立集合逐步合并相邻的集合最终统计剩余集合数量。这种方法的优势在于不需要修改原始网格可以增量处理数据适合动态变化的场景5.2 完整实现代码class Solution { public: vectorint parent; int count 0; int find(int x) { while(parent[x] ! x) { parent[x] parent[parent[x]]; // 路径压缩 x parent[x]; } return x; } void unite(int x, int y) { int rootX find(x); int rootY find(y); if(rootX ! rootY) { parent[rootX] rootY; --count; } } int numIslands(vectorvectorchar grid) { if(grid.empty()) return 0; int m grid.size(), n grid[0].size(); parent.resize(m*n); // 初始化 for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1) { parent[i*n j] i*n j; count; } } } // 合并操作 for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1) { if(i 0 grid[i-1][j] 1) unite(i*n j, (i-1)*n j); if(j 0 grid[i][j-1] 1) unite(i*n j, i*n j-1); } } } return count; } };并查集的性能约28ms虽然不如DFS/BFS快但在某些特殊场景下如动态变化的网格更有优势。6. 算法选择与优化技巧经过多次实践我总结出以下经验面试时优先实现DFS代码简洁易懂竞赛中可以考虑BFS避免递归风险并查集适合作为加分项展示优化技巧方向数组简化代码int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}};提前检查空输入使用位运算优化并查集在真实项目中我曾遇到需要处理TB级地图数据的情况最终采用分块BFS的方案每个区块独立处理后再合并结果。这种思路也可以应用到这道题的变种中。