力扣HOT100（34）图论-岛屿数量

方法一：深度优先搜索（DFS，面试首选）

1. 核心思路

我们把网格看作一个无向图：

• 每个'1'是一个顶点
• 上下左右相邻的'1'之间有边相连

解题步骤：

1. 遍历整个网格，遇到'1'说明发现了新岛屿，岛屿数 + 1
2. 以这个'1'为起点，进行 DFS 遍历：
   • 把当前'1'改成'0'（标记为已访问，避免重复统计）
   • 递归遍历它的上下左右四个方向，遇到'1'就继续递归
3. 一次 DFS 会把整个连通的岛屿全部标记为 0，后续遍历不会再遇到这些点
4. 最终 DFS 的次数，就是岛屿的数量

class Solution { public: //写一个深度优先的函数 void dfs(vector<vector<char>>& grid,int r,int c){ //需要传入的参数是一个矩阵grid 开始的起点的行数和列数 int nr = grid.size();//行数 int nc = grid[0].size();//列数 grid[r][c] = '0';//首先上来把这个位置的点记成0，防止下次找到他 //上面的数如果是1：那就对这个1进行搜索 if(r-1 >=0&&grid[r-1][c] == '1') dfs(grid,r-1,c); //下面： if(r+1 < nr&&grid[r+1][c] == '1') dfs(grid, r + 1, c); if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1); if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1); } int numIslands(vector<vector<char>>& grid) { //核心思路：利用深度优先搜索法 找到一个1以后就对上下左右进行搜索，然后把岛屿数+1，并把这个1标记为0. int nr = grid.size(); if(!nr){ return 0; } int nc = grid[0].size(); int num_islands = 0;//记录岛屿的数量 for(int r = 0;r<nr;r++){ for(int c = 0;c<nc;c++){ if(grid[r][c] =='1'){ ++num_islands; //开始遍历 如果某个位置的数是1，那么开始深度搜素 dfs(grid,r,c); } } } return num_islands; } };

方法二：广度优先搜索（BFS，无栈溢出风险）

1. 核心思路

和 DFS 逻辑完全等价，只是用队列代替递归栈，避免大网格下的栈溢出问题：

1. 遍历网格，遇到'1'岛屿数 + 1
2. 把当前'1'入队，标记为'0'
3. 队列不为空时，取出队首节点，把它的上下左右四个方向的'1'入队并标记为'0'
4. 队列为空时，当前岛屿遍历完成，继续找下一个'1'

class Solution { public: int numIslands(vector<vector<char>>& grid) { int nr = grid.size(); if(!nr) return 0; int nc = grid[0].size(); int num_islands = 0; for(int r = 0;r< nr;++r){ for(int c = 0;c<nc;++c){ if(grid[r][c] == '1'){ ++num_islands; grid[r][c] = '0'; queue<pair<int,int>> neighbors;//创建队列 存pair neighbors.push({r,c});//把该点坐标存进去 while(!neighbors.empty()){ //不为空则循环 auto rc = neighbors.front(); neighbors.pop(); int row = rc.first, col = rc.second; if (row - 1 >= 0 && grid[row-1][col] == '1') { neighbors.push({row-1, col}); grid[row-1][col] = '0'; } if (row + 1 < nr && grid[row+1][col] == '1') { neighbors.push({row+1, col}); grid[row+1][col] = '0'; } if (col - 1 >= 0 && grid[row][col-1] == '1') { neighbors.push({row, col-1}); grid[row][col-1] = '0'; } if (col + 1 < nc && grid[row][col+1] == '1') { neighbors.push({row, col+1}); grid[row][col+1] = '0'; } } } } } return num_islands; } };