图论day56|广度优先搜索理论基础 、bfs与dfs的对比(思维导图)、 99.岛屿数量(卡码网)、100.岛屿的最大面积(卡码网)

时间:2024-10-10 14:45:57

图论day56|广度优先搜索理论基础 、bfs与dfs的对比(思维导图)、 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(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; // 只要加入队列立刻标记,避免重复访问
            }
        }
    }

}

要素:

  • 表示方向的二维数组
  • 表示地图的二维数组
  • 表示是否访问的二维数组
  • 坐标的数据类型
  • 能存储坐标的队列
  • 当前结点(curx,cury)和下一个结点坐标(nextx,nexty)

代码思路:将起始点存入队列并获取当前元素,再根据当前元素获取下一个元素,并存入队列

(以上主要摘自代码随想录)

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

提示信息

img

根据测试案例中所展示,岛屿数量共有 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 vector<vector<int>> &grid,vector<vector<bool>> &visited,int x,int y)
{
    if(grid[x][y]==0||visited[x][y])
        return;
    visited[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[1].size())
            continue;
        dfs(grid,visited,nextx,nexty);
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>grid[i][j];
        }
    vector<vector<bool>> visited(n+1,vector<bool>(m+1,false));
    int result=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(grid[i][j]==1&&!visited[i][j])
            {
                result++;
                dfs(grid,visited,i,j);
            }
    cout<<result<<endl;
    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(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[1].size())
                continue;
            if(grid[nextx][nexty]==1&&visited[nextx][nexty]==false)
            {
                que.push({nextx,nexty});
                visited[nextx][nexty]=true;
            }
        }
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>grid[i][j];
    vector<vector<bool>> visited(n+1,vector<bool>(m+1,false));
    int result=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(visited[i][j]==false&&grid[i][j]==1)
            {
                result++;
                bfs(grid,visited,i,j);
            }
    cout<<result<<endl;
}

分析思路如下:

在这里插入图片描述

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

提示信息

img

样例输入中,岛屿的最大面积为 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(vector<vector<int>> grid,vector<vector<bool>> &visited,int x,int y,int &area)
{
    queue<pair<int,int>> que;
    que.push({x,y});
    visited[x][y]=true;
    area++;
    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[1].size())
                continue;
            if(grid[nextx][nexty]==1&&visited[nextx][nexty]==false)
            {
                que.push({nextx,nexty});
                visited[nextx][nexty]=true;
                area++;
            }
        }
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>grid[i][j];
    vector<vector<bool>> visited(n+1,vector<bool>(m+1,false));
    int maxArea=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(visited[i][j]==false&&grid[i][j]==1)
            {
                int area=0;
                bfs(grid,visited,i,j,area);
                maxArea=max(maxArea,area);
            }
    cout<<maxArea<<endl;
}

在99题的基础上加一个area即可,基本没有难度