蓝色机械企业网站模板,网站建设过程与思路,政协网站建设,创意设计产业图论day56|广度优先搜索理论基础 、bfs与dfs的对比#xff08;思维导图#xff09;、 99.岛屿数量#xff08;卡码网#xff09;、100.岛屿的最大面积#xff08;卡码网#xff09;#xff09; 广度优先搜索理论基础bfs与dfs的对比#xff08;思维导图#xff09;思维导图、 99.岛屿数量卡码网、100.岛屿的最大面积卡码网 广度优先搜索理论基础bfs与dfs的对比思维导图 99.岛屿数量(卡码网)1.深搜法2.广搜法 100.岛屿的最大面积卡码网) 广度优先搜索理论基础 应用场景 适合于解决两个点之间的最短路径问题不涉及具体的遍历方式深搜和广搜都可以 广搜bfs的过程 代码框架
int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图也就是一个二维数组
// visited标记访问过的节点不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y) {queuepairint, int que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] true; // 只要加入队列立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pairint ,int cur que.front(); que.pop(); // 从队列取元素int curx cur.first;int cury cur.second; // 当前节点坐标for (int i 0; i 4; i) { // 开始想当前节点的四个方向左右上下去遍历int nextx curx dir[i][0];int nexty cury dir[i][1]; // 获取周边四个方向的坐标if (nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue; // 坐标越界了直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] true; // 只要加入队列立刻标记避免重复访问}}}}要素
表示方向的二维数组表示地图的二维数组表示是否访问的二维数组坐标的数据类型能存储坐标的队列当前结点curxcury和下一个结点坐标nextxnexty
代码思路将起始点存入队列并获取当前元素再根据当前元素获取下一个元素并存入队列
以上主要摘自代码随想录
bfs与dfs的对比思维导图 99.岛屿数量(卡码网)
题目描述
给定一个由 1陆地和 0水组成的矩阵你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M表示矩阵的行数和列数。
后续 N 行每行包含 M 个数字数字为 1 或者 0。
输出描述
输出一个整数表示岛屿的数量。如果不存在岛屿则输出 0。
输入示例
4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1
输出示例
3
提示信息 根据测试案例中所展示岛屿数量共有 3 个所以输出 3。
数据范围
1 N, M 50
1.深搜法
#include iostream
#include vector
using namespace std;int dir[4][2]{0, 1, 1, 0, -1, 0, 0, -1};void dfs(const vectorvectorint grid,vectorvectorbool visited,int x,int y)
{if(grid[x][y]0||visited[x][y])return;visited[x][y]true;for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[1].size())continue;dfs(grid,visited,nextx,nexty);}
}int main()
{int n,m;cinnm;vectorvectorint grid(n1,vectorint(m1,0));for(int i1;in;i)for(int j1;jm;j){cingrid[i][j];}vectorvectorbool visited(n1,vectorbool(m1,false));int result0;for(int i1;in;i)for(int j1;jm;j)if(grid[i][j]1!visited[i][j]){result;dfs(grid,visited,i,j);}coutresultendl;return 0;
}2.广搜法
#include iostream
#include vector
#include queue
using namespace std;int dir[4][2]{1,0,-1,0,0,1,0,-1};
void bfs(vectorvectorint grid,vectorvectorbool visited,int x,int y)
{queuepairint,int que;que.push({x,y});visited[x][y]true;while(!que.empty()){pairint,int curque.front();que.pop();int curxcur.first;int curycur.second;for(int i0;i4;i){int nextxcurxdir[i][0];int nextycurydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[1].size())continue;if(grid[nextx][nexty]1visited[nextx][nexty]false){que.push({nextx,nexty});visited[nextx][nexty]true;}}}
}int main()
{int n,m;cinnm;vectorvectorint grid(n1,vectorint(m1,0));for(int i1;in;i)for(int j1;jm;j)cingrid[i][j];vectorvectorbool visited(n1,vectorbool(m1,false));int result0;for(int i1;in;i)for(int j1;jm;j)if(visited[i][j]falsegrid[i][j]1){result;bfs(grid,visited,i,j);}coutresultendl;
}分析思路如下 100.岛屿的最大面积卡码网)
题目描述
给定一个由 1陆地和 0水组成的矩阵计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M表示矩阵的行数和列数。后续 N 行每行包含 M 个数字数字为 1 或者 0表示岛屿的单元格。
输出描述
输出一个整数表示岛屿的最大面积。如果不存在岛屿则输出 0。
输入示例
4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1
输出示例
4
提示信息 样例输入中岛屿的最大面积为 4。
数据范围
1 M, N 50。
#include iostream
#include vector
#include queue
using namespace std;int dir[4][2]{1,0,-1,0,0,1,0,-1};
void bfs(vectorvectorint grid,vectorvectorbool visited,int x,int y,int area)
{queuepairint,int que;que.push({x,y});visited[x][y]true;area;while(!que.empty()){pairint,int curque.front();que.pop();int curxcur.first;int curycur.second;for(int i0;i4;i){int nextxcurxdir[i][0];int nextycurydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[1].size())continue;if(grid[nextx][nexty]1visited[nextx][nexty]false){que.push({nextx,nexty});visited[nextx][nexty]true;area;}}}
}int main()
{int n,m;cinnm;vectorvectorint grid(n1,vectorint(m1,0));for(int i1;in;i)for(int j1;jm;j)cingrid[i][j];vectorvectorbool visited(n1,vectorbool(m1,false));int maxArea0;for(int i1;in;i)for(int j1;jm;j)if(visited[i][j]falsegrid[i][j]1){int area0;bfs(grid,visited,i,j,area);maxAreamax(maxArea,area);}coutmaxAreaendl;
}在99题的基础上加一个area即可基本没有难度
