从岛屿问题掌握网格DFSLeetCode 200题三维解法全解析第一次看到LeetCode 200题岛屿数量时很多人会被二维网格中那些孤立的1和0搞得晕头转向。这看似简单的题目背后隐藏着深度优先搜索(DFS)最精妙的应用场景——网格遍历。不同于树结构的DFS网格DFS有着独特的遍历逻辑和边界处理方式这正是算法初学者最容易栽跟头的地方。本文将带你从零开始用三种不同视角彻底吃透这道经典题目。我们不仅会用动态图解拆解DFS的核心思想还会对比广度优先搜索(BFS)的实现差异最后引入并查集这种高效的数据结构解法。无论你是视觉型学习者还是代码实践派都能在这里找到适合自己的理解路径。1. 网格DFS的本质与可视化拆解网格DFS最让人困惑的地方在于它看起来像树遍历但实际处理起来却大不相同。在二叉树中我们只需要递归访问左右子节点而在网格中每个点可能有四个方向需要探索上下左右。这种多维度的扩展性正是网格问题的独特魅力。1.1 基础DFS解法框架让我们先看最基础的DFS实现代码class Solution { public: void dfs(vectorvectorchar grid, int i, int j) { grid[i][j] 0; // 标记已访问 // 四个方向的探索 if(i 0 grid[i-1][j] 1) dfs(grid, i-1, j); // 上 if(i grid.size()-1 grid[i1][j] 1) dfs(grid, i1, j); // 下 if(j 0 grid[i][j-1] 1) dfs(grid, i, j-1); // 左 if(j grid[0].size()-1 grid[i][j1] 1) dfs(grid, i, j1); // 右 } int numIslands(vectorvectorchar grid) { 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; } };这段代码中有几个关键点需要特别注意原地修改网格我们直接将访问过的1改为0这既标记了已访问又防止了重复计数边界检查每个方向的递归前都必须检查是否越界主循环逻辑外层循环负责发现新岛屿的种子内层DFS负责染色整个岛屿1.2 递归过程的可视化理解为了更直观地理解DFS如何淹没整个岛屿让我们看一个具体的例子原始网格 [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]执行过程可以分解为以下步骤(0,0)发现1开始DFS淹没(0,0)探索上方越界跳过探索下方(1,0)是1递归淹没(1,0)上方(0,0)已是0跳过下方(2,0)是0跳过左方越界跳过右方(1,1)是1递归淹没(1,1)上方(0,1)是1递归淹没(0,1)所有相邻都检查完毕其他方向检查完毕其他方向检查完毕岛屿计数1继续扫描在(2,2)发现新1开始DFS淹没(2,2)所有相邻都是0递归结束岛屿计数1在(3,3)发现1开始DFS淹没(3,3)右方(3,4)是1递归淹没(3,4)所有相邻检查完毕岛屿计数1最终结果3提示在纸上画出网格用不同颜色标记访问过程是理解DFS遍历顺序的最佳方式。2. BFS解法队列驱动的层序遍历虽然DFS是解决岛屿问题的自然思路但广度优先搜索(BFS)同样能胜任这项工作。两者的核心区别在于探索顺序DFS像探险家一样勇往直前直到无路可走才回头而BFS则像波纹扩散一样逐层推进。2.1 BFS实现代码解析class Solution { public: int numIslands(vectorvectorchar grid) { int rows grid.size(); if(rows 0) return 0; int cols grid[0].size(); int islands 0; for(int i 0; i rows; i) { for(int j 0; j cols; j) { if(grid[i][j] 1) { islands; queuepairint,int q; q.push({i,j}); grid[i][j] 0; while(!q.empty()) { auto curr q.front(); q.pop(); int x curr.first, y curr.second; // 检查四个方向 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 islands; } };2.2 BFS与DFS的关键差异特性DFSBFS数据结构递归栈/显式栈队列内存消耗最坏O(MN)平均O(max(M,N))访问顺序深度优先广度优先实现难度递归简单需手动管理队列适用场景寻找连通区域最短路径问题注意在BFS实现中必须在入队时立即标记已访问而不是出队时标记否则可能导致同一节点被多次入队引发性能问题。3. 并查集优雅的连通性解决方案对于岛屿问题并查集(Union-Find)提供了一种完全不同的解决思路。它不关注遍历顺序而是专注于动态维护连通分量之间的关系。3.1 并查集核心操作并查集主要支持两种操作Find确定元素属于哪个子集Union将两个子集合并为一个集合class UnionFind { public: UnionFind(vectorvectorchar grid) { count 0; int m grid.size(); int n grid[0].size(); parent vectorint(m*n); rank vectorint(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; } rank[i*n j] 0; } } } int find(int i) { if(parent[i] ! i) { parent[i] find(parent[i]); // 路径压缩 } return parent[i]; } void unite(int x, int y) { int rootx find(x); int rooty find(y); if(rootx ! rooty) { if(rank[rootx] rank[rooty]) { parent[rootx] rooty; } else { parent[rooty] rootx; if(rank[rootx] rank[rooty]) rank[rootx]; } --count; } } int getCount() const { return count; } private: vectorint parent; vectorint rank; int count; };3.2 并查集解决岛屿问题class Solution { public: int numIslands(vectorvectorchar grid) { if(grid.empty() || grid[0].empty()) return 0; int m grid.size(); int n grid[0].size(); UnionFind uf(grid); for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1) { grid[i][j] 0; // 可省略因为并查集不依赖网格状态 if(i - 1 0 grid[i-1][j] 1) { uf.unite(i*nj, (i-1)*nj); } if(j - 1 0 grid[i][j-1] 1) { uf.unite(i*nj, i*nj-1); } } } } return uf.getCount(); } };并查集的优势在于不需要修改原始网格数据可以动态处理网格变化时间复杂度接近线性(O(MNα(MN))其中α是反阿克曼函数)4. 三种解法的性能对比与选择建议在实际应用中不同解法各有优劣。下面我们从多个维度进行对比分析4.1 时间复杂度比较解法时间复杂度空间复杂度适用场景DFSO(MN)O(MN)简单直观递归深度可控BFSO(MN)O(MN)需要最短路径信息并查集O(MNα(MN))O(MN)动态连通性问题4.2 实际测试数据在LeetCode测试用例上三种解法的表现如下解法运行时间(ms)内存消耗(MB)代码复杂度DFS2811.9★★☆☆☆BFS3214.2★★★☆☆并查集3612.1★★★★☆4.3 选择建议面试场景优先展示DFS解法它最直观且易于解释竞赛场景并查集可能更高效特别是需要处理动态变化时工程应用BFS通常更安全避免递归栈溢出风险在解决类似网格问题时我通常会先尝试DFS实现因为它写起来最顺手。但当遇到特别大的网格时会切换到BFS版本以防栈溢出。而并查集则保留给那些需要频繁查询连通性的特殊场景。