c++给定无向图的顶点数、边数以及边的信息,输出无向图深度优先搜索遍历序列。X组测试数据,对于每组测试数据, 第一行输入顶点数N(N<=100),边数M,数据之间空格分隔; 第二行输入M条边的信息(v1 v2表示边的顶点),数据之间由空格分隔。输出无向图深度优先搜索遍历序列,各顶点之间用空格分隔。
时间: 2024-03-21 10:43:26 浏览: 65
好的,这是一个关于深度优先搜索遍历无向图的问题。下面是C++的解决方案:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
vector<int> G[MAXN + 1];
bool vis[MAXN + 1];
void dfs(int u) {
vis[u] = true;
cout << u << " ";
for (int v : G[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; 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]) {
dfs(i);
}
}
return 0;
}
```
首先,我们用邻接表来存储无向图。然后,我们用一个布尔数组`vis`来记录每个顶点是否已被访问过。在`dfs`函数中,我们首先将当前顶点`u`标记为已访问,并输出它。然后,我们遍历`u`的所有邻居`v`,如果`v`还没有被访问过,则递归调用`dfs(v)`。最后,在`main`函数中,我们遍历所有顶点,如果一个顶点还没有被访问过,则从它开始进行深度优先搜索。
希望能够帮到你!
阅读全文