用c++实现深度优先搜索
时间: 2023-08-24 07:34:32 浏览: 43
以下是使用C++实现深度优先搜索的示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大节点数
bool vis[MAXN]; // 记录节点是否已经被访问
vector<int> g[MAXN]; // 图的邻接表
void dfs(int u) {
vis[u] = true; // 标记节点已经被访问
cout << u << " "; // 输出当前节点
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
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); // 无向图需要添加反向边
}
memset(vis, false, sizeof(vis)); // 初始化节点为未访问
for (int i = 1; i <= n; i++) {
if (!vis[i]) { // 如果节点未被访问,从该节点开始搜索
dfs(i);
}
}
return 0;
}
```
在以上代码中,我们使用邻接表表示图,并使用一个布尔数组`vis`记录节点是否已经被访问。`dfs`函数接受一个参数`u`,表示当前搜索的节点。在搜索过程中,我们首先将该节点标记为已访问,然后输出当前节点,并继续遍历该节点的未被访问的邻居节点。最后,我们在`main`函数中遍历所有节点,如果该节点未被访问,则从该节点开始搜索。