代码随想录算法训练营第五十一天|图论part2

思路：

先将岛屿数据存储到二维矩阵，遍历二维矩阵，遇到1，则统计数量+1，然后将该岛屿四个方向的岛屿都标为已访问。

记得处理边界情况

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(vector<vector<int>>graph,vector<vector<bool>>&isvisited,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<1||nextx>=graph.size()||nexty<1||nexty>=graph[0].size())continue;
        if(graph[nextx][nexty]==1&&!isvisited[nextx][nexty]){
            isvisited[nextx][nexty]=true;
            dfs(graph,isvisited,nextx,nexty);
        }
    }  
}

int main(){
    int n,m,x;
    cin>>n>>m;
    vector<vector<int>>graph(n+1,vector<int>(m+1,1));
    vector<vector<bool>>isvisited(n+1,vector<bool>(m+1,false));
    for(int i=1;i<=n;i++){                  //用二维矩阵存储图
        for(int j=1;j<=m;j++){
            cin>>x;
            graph[i][j]=x;
        }
    }

    int result=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!isvisited[i][j]&&graph[i][j]){
                isvisited[i][j]=true;
                result++;
                dfs(graph,isvisited,i,j);  //将相连的陆地标记为已访问
            }
        }
    }
    cout<<result<<endl;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void bfs(vector<vector<int>>graph,vector<vector<bool>>&isvisited,int x,int y){
    queue<pair<int,int>>mq;
    mq.push({x,y});    //注意pair的用法
    while(!mq.empty()){
        auto current = mq.front();  // ✅ 取出当前节点!!!!!!!!!!
        mq.pop();
        int curx = current.first;
        int cury = current.second;
        for(int i=0;i<4;i++){//考虑四个方向
            int nextx=curx+dir[i][0];
            int nexty=cury+dir[i][1];
            if(nextx<1||nextx>=graph.size()||nexty<1||nexty>=graph[0].size())continue;
            if(graph[nextx][nexty]==1&&!isvisited[nextx][nexty]){
                isvisited[nextx][nexty]=true;
                mq.push({nextx,nexty});
            }
        }
    }

}

int main(){
    int n,m,x;
    cin>>n>>m;
    vector<vector<int>>graph(n+1,vector<int>(m+1,1));
    vector<vector<bool>>isvisited(n+1,vector<bool>(m+1,false));
    for(int i=1;i<=n;i++){                  //用二维矩阵存储图
        for(int j=1;j<=m;j++){
            cin>>x;
            graph[i][j]=x;
        }
    }

    int result=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!isvisited[i][j]&&graph[i][j]){
                isvisited[i][j]=true;
                result++;
                bfs(graph,isvisited,i,j);  //将相连的陆地标记为已访问
            }
        }
    }
    cout<<result<<endl;
}

广度优先搜索遍历：

新建一个队列，当前节点入队，

while队列不为空，获取队首节点，处理当前节点逻辑，符合条件的入队。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
//深度优先
void dfs(vector<vector<int>>graph,vector<vector<bool>>&visited,int &area,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>=graph.size()||nexty<0||nexty>graph[0].size()) continue;
        if(graph[nextx][nexty]==1&&!visited[nextx][nexty]){
            visited[nextx][nexty]=true;
            area++;
            dfs(graph,visited,area,nextx,nexty);
        }
    }
}
//广度优先
void bfs(vector<vector<int>>graph,vector<vector<bool>>&visited,int &area,int x, int y){
    queue<pair<int,int>>mq;    
    mq.push({x,y});                //当前节点入队
    while(!mq.empty()){
        auto curnode=mq.front();   //队首节点出队
        mq.pop();
        int curx=curnode.first;
        int cury=curnode.second;
        for(int i=0;i<4;i++){     //处理当前节点有联系的
            int nextx=curx+dir[i][0];
            int nexty=cury+dir[i][1];
            if(nextx<0||nextx>=graph.size()||nexty<0||nexty>graph[0].size()) continue;
            if(graph[nextx][nexty]==1&&!visited[nextx][nexty]){
                visited[nextx][nexty]=true;
                area++;
            mq.push({nextx,nexty});  //有联系的入队
        }
    }
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>graph(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>graph[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(graph[i][j]==1&&!visited[i][j]){
                int area=1;
                visited[i][j]=true;
                bfs(graph,visited,area,i,j);
                // dfs(graph,visited,area,i,j);
                maxArea=max(maxArea,area);
            }
        }
    }
    cout<<maxArea<<endl;
}