c++给定无向图的顶点数、边数以及边的信息,输出无向图广度优先搜索遍历序列。X组测试数据,对于每组测试数据, 第一行输入顶点数N(N<=100),边数M,数据之间空格分隔; 第二行输入M条边的信息(v1 v2表示边的顶点),数据之间由空格分隔。输出无向图广度优先搜索遍历序列,各顶点之间用空格分隔。
时间: 2024-03-22 18:38:13 浏览: 21
好的,这是一个关于无向图广度优先搜索遍历的问题,我可以帮您解答。
以下是C++代码实现:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 105;
vector<int> G[MAXN];
bool vis[MAXN];
void bfs(int s) {
queue<int> q;
q.push(s);
vis[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
bfs(i);
}
}
cout << endl;
return 0;
}
```
代码思路解析:
1. 建图:通过输入的边信息构建邻接表G。
2. 遍历:从每个未被访问的节点开始,进行广度优先搜索。
3. 标记:访问过的节点进行标记,避免重复访问。
其中,vis数组用于标记节点是否被访问过,queue用于存储待访问的节点。
希望这个代码能够帮助你解决问题,如果您还有任何疑问,可以继续问我。