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

方法一深度优先搜索DFS面试首选1. 核心思路我们把网格看作一个无向图每个1是一个顶点上下左右相邻的1之间有边相连解题步骤遍历整个网格遇到1说明发现了新岛屿岛屿数 1以这个1为起点进行 DFS 遍历把当前1改成0标记为已访问避免重复统计递归遍历它的上下左右四个方向遇到1就继续递归一次 DFS 会把整个连通的岛屿全部标记为 0后续遍历不会再遇到这些点最终 DFS 的次数就是岛屿的数量class Solution { public: //写一个深度优先的函数 void dfs(vectorvectorchar 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 0grid[r-1][c] 1) dfs(grid,r-1,c); //下面 if(r1 nrgrid[r1][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][c1] 1) dfs(grid, r, c 1); } int numIslands(vectorvectorchar 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;rnr;r){ for(int c 0;cnc;c){ if(grid[r][c] 1){ num_islands; //开始遍历 如果某个位置的数是1那么开始深度搜素 dfs(grid,r,c); } } } return num_islands; } };方法二广度优先搜索BFS无栈溢出风险1. 核心思路和 DFS 逻辑完全等价只是用队列代替递归栈避免大网格下的栈溢出问题遍历网格遇到1岛屿数 1把当前1入队标记为0队列不为空时取出队首节点把它的上下左右四个方向的1入队并标记为0队列为空时当前岛屿遍历完成继续找下一个1class Solution { public: int numIslands(vectorvectorchar 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;cnc;c){ if(grid[r][c] 1){ num_islands; grid[r][c] 0; queuepairint,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[row1][col] 1) { neighbors.push({row1, col}); grid[row1][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][col1] 1) { neighbors.push({row, col1}); grid[row][col1] 0; } } } } } return num_islands; } };