对输入的无向图进行深度优先搜索遍历c++
时间: 2024-03-12 19:49:35 浏览: 21
好的,以下是一个对输入的无向图进行深度优先搜索遍历的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大结点数
vector<int> G[MAXN]; // 图的邻接表表示
bool visited[MAXN]; // 记录结点是否已经访问
void dfs(int u) {
visited[u] = true; // 标记 u 为已访问
// 遍历所有与 u 相邻的未访问结点
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!visited[v]) {
dfs(v);
}
}
}
int main() {
int n, m; // 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); // 若是无向图,则需要存储反向边
}
// 从结点 1 开始深度优先搜索
dfs(1);
return 0;
}
```
在这个代码示例中,我们采用了邻接表来表示图。对于每个还未访问的结点,我们调用dfs函数进行递归遍历。在dfs函数中,我们将当前结点标记为已访问,然后遍历其所有相邻的未访问结点,再对这些相邻结点分别递归调用dfs函数。这样就完成了深度优先搜索遍历。
需要注意的是,这个代码示例中使用的是递归实现方式。如果图非常大,可能会导致栈溢出。因此,建议使用如上述非递归实现方式的代码示例中所示的非递归实现方式。