c++深度优先搜索的实现
时间: 2023-12-18 11:26:58 浏览: 29
深度优先搜索是一种非常重要的图遍历算法,它可以用来解决很多实际问题。下面是C++实现深度优先搜索的方法:
1. 首先定义一个visited数组,用来记录每个顶点是否被访问过。
2. 然后定义一个dfs函数,该函数接受一个图和一个起始顶点作为参数。在dfs函数中,首先将当前顶点标记为已访问,然后遍历当前顶点的所有邻居节点,如果邻居节点没有被访问过,则递归调用dfs函数。
3. 最后,在主函数中调用dfs函数,从图的某一个顶点开始遍历整个图。
下面是C++代码实现:
```
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000;
vector<int> G[MAXN]; // 图的邻接表表示
bool visited[MAXN]; // 记录每个顶点是否被访问过
void dfs(int u) {
visited[u] = true; // 标记当前顶点为已访问
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i]; // 遍历当前顶点的所有邻居节点
if (!visited[v]) {
dfs(v); // 递归调用dfs函数
}
}
}
int main() {
// 构建图的邻接表表示
G[0].push_back(1);
G[0].push_back(2);
G[1].push_back(2);
G[2].push_back(0);
G[2].push_back(3);
G[3].push_back(3);
// 从顶点2开始遍历整个图
dfs(2);
return 0;
}
```