算法日记 42 day 图论
今天来看看广度优先搜索，并且写几个题。刷到这里我才想起来，当时第一次面试的时候问的就是这个题，当时大概知道一点思路，但不清楚是图论方面的，更别说写出来了。
广度优先搜索（BFS）
不同于深度优先，广度优先讲究的是先遍历完一层，在遍历下一层，就这转圈圈，直到遍历完所有。就像这样
那么对于广搜的写法来说，不管是队列，栈，或者数组都可以。不过方便遍历，大多使用的是队列，接下来的题目我也使用队列。
那么广搜的代码大概什么样子呢？
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> que; // 定义队列
que.push({x, y}); // 起始节点加入队列
visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
while(!que.empty()) { // 开始遍历队列里的元素
pair<int ,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; // 只要加入队列立刻标记，避免重复访问
}
}
}
}接下来的题目中，我们都会使用到。
题目：岛屿数量
给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。
后续 N 行，每行包含 M 个数字，数字为 1 或者 0。
输出描述
输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。
题目分析：
很明显的搜索题，我们分别看看广度和深度的写法。不过对于深搜而言，有两种不同的写法，区别在于终止条件的写法，一个写在递归之前，一个写在循环遍历里面。
深搜第一种：
#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void DFS(const vector<vector<int>>& grid,vector<vector<bool>>& visite,int x,int y){
if(visite[x][y]||grid[x][y]==0) return;//节点访问过或者是海洋区域
visite[x][y]=true;
for(int i=0;i<4;i++){
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳过
DFS(grid, visite, nextx, nexty);
}
}
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> grid(n,vector<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
vector<vector<bool>> visite(n,vector<bool>(m,false));//标记数组
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visite[i][j]&&grid[i][j]==1)//当前 节点没有访问过，并且是陆地
{
res++;
DFS(grid,visite,i,j);
}
}
}
cout<<res<<endl;
}深搜第二种：
#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void DFS(const vector<vector<int>>& grid,vector<vector<bool>>& visite,int x,int y){
for(int i=0;i<4;i++){
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()) continue;
if(!visite[nextx][nexty]&&grid[nextx][nexty]==1){
visite[nextx][nexty]=true;
DFS(grid,visite,nextx,nexty);
}
}
}
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> grid(n,vector<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
vector<vector<bool>> visite(n,vector<bool>(m,false));//标记数组
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visite[i][j]&&grid[i][j]==1)//当前 节点没有访问过，并且是陆地
{
visite[i][j]=true;
res++;
DFS(grid,visite,i,j);
}
}
}
cout<<res<<endl;
}广搜：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> que; //你也可以单纯的使用队列，不过出队和入队时需要进行两次
que.push({x, y});
visited[x][y] = true; // 只要加入队列，立刻标记
while(!que.empty()) {
pair<int ,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] && grid[nextx][nexty] == 1) {
que.push({nextx, nexty});
visited[nextx][nexty] = true; // 只要加入队列立刻标记
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
vector<vector<bool>> visited(n, vector<bool>(m, false));
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
result++; // 遇到没访问过的陆地，+1
bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
}
}
}
cout << result << endl;
}题目：岛屿的最大面积
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。
题目分析：
和上一题一样，注意岛屿面积收集的位置即可
深搜第一种：
#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向//逆时针
int count;
void DFS(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){
for(int i=0;i<4;i++){
int nextX=x+dir[i][0];
int nextY=y+dir[i][1];
if(nextX<0||nextX>=grid.size()||nextY<0||nextY>=grid[0].size()) continue;
if(!visited[nextX][nextY]&&grid[nextX][nextY]==1){
count++;
visited[nextX][nextY]=true;
DFS(grid,visited,nextX,nextY);
}
}
}
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> grid(n,vector<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
vector<vector<bool>> visited(n,vector<bool>(m,false));
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visited[i][j]&&grid[i][j]==1){
count=1;
visited[i][j]=true;
DFS(grid,visited,i,j);
res=max(res,count);
}
}
}
cout << res<<endl;
}深搜第二种：
#include<iostream>
#include<vector>
using namespace std;
int dir[4][2]={0,1,1,0,-1,0,0,-1};
int count;
void DFS(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){
if(visited[x][y]||grid[x][y]==0) return;
visited[x][y]=true;
count++;
for(int i=0;i<4;i++){
int nextx=x+dir[i][0];
int nexty=y+dir[i][1];
if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()) continue;
DFS(grid,visited,nextx,nexty);
}
}
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> grid(n,vector<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
vector<vector<bool>> visited(n,vector<bool>(m,false));
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visited[i][j]&&grid[i][j]==1){
count=0;
DFS(grid,visited,i,j);
res=max(res,count);
}
}
}
cout << res<<endl;
}广搜：
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int dir[4][2]={0,1,1,0,-1,0,0,-1};
int count;
void BFS(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){
queue<pair<int,int>> que;
que.push({x,y});
visited[x][y]=true;
count++;
while(!que.empty()){
pair<int,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]&&grid[nextx][nexty]==1){
que.push({nextx,nexty});
count++;
visited[nextx][nexty]=true;
}
}
}
}
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> grid(n,vector<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
vector<vector<bool>> visited(n,vector<bool>(m,false));
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visited[i][j]&&grid[i][j]==1){
count=0;
BFS(grid,visited,i,j);
res=max(res,count);
}
}
}
cout << res<<endl;
}对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。
已刷题目：132
原文地址：https://blog.csdn.net/weixin_70808146/article/details/144275866
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！