图的广搜遍历
2025-08-18 15:29:23
发布于：浙江
11阅读
0回复
0点赞
对于图的遍历，广搜是其中一种遍历方法之一
例：
给定一个无向图，
第一行输入两个数字n,m，分别代表无向图的顶点数和边数
接下来m行，输入两个数字u,v代表u,v间有一条无向边，保证该图是连通图
遍历所有节点并输出
这里采用了邻接表的方法:
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m;
bool flag[100010];//标记数组
vector<int> pic[100010];//邻接表(动态二维数组)：统计无向边
void bfs(int x){//广搜
queue<int> q;
q.push(x);
flag[x] = 1;//初始化
while(!q.empty()){
int t = q.front();
q.pop();
cout << t << " ";
for(int i = 0;i < pic[t].size();i++){
if(flag[pic[t][i]] == 0){
flag[pic[t][i]] = 1;
q.push(pic[t][i]);
}
}
}
}
int main(){
cin >> n >> m;
while(m--){
int u,v;
cin >> u >> v;
pic[u].push_back(v);
pic[v].push_back(u);//无向图双向存储
}
bfs(1);//从1开始遍历
return 0;
}
这里空空如也
有帮助，赞一个