请用dfs写出c++.
时间: 2024-10-19 16:12:00 浏览: 22
深度优先搜索(Depth First Search,DFS)是一种用于遍历或搜索树形结构以及图的算法。在C++中,你可以使用递归的方式来实现DFS。以下是一个简单的例子,展示如何使用DFS遍历无向图中的节点:
```cpp
#include <iostream>
#include <vector>
#include <stack>
// 图的邻接表表示
std::vector<std::vector<int>> adjList;
// 记录已访问节点的辅助栈
std::stack<int> stack;
// DFS 函数,接受当前节点
void dfs(int node) {
// 标记当前节点为已访问
std::cout << "Visiting node: " << node << std::endl;
// 将当前节点压入栈中
stack.push(node);
// 遍历当前节点的所有邻居
for (int neighbor : adjList[node]) {
// 如果邻居未被访问过
if (!visited[neighbor]) { // visited 是记录节点是否访问过的数组
// 对邻居进行深搜
dfs(neighbor);
}
}
// 当访问完所有邻居后,回溯到上一级
stack.pop();
}
int main() {
// 初始化图的数据(这里假设你已经有了一个邻接列表表示)
// ...
// 对于每个需要进行DFS的起始节点,调用dfs函数
for (int startNode : startingNodes) {
visited[startNode] = true; // 初始化访问标志
dfs(startNode);
}
return 0;
}
```
在这个示例中,`adjList`存储了图的邻接矩阵,`visited`数组用于标记节点是否已被访问。DFS通过递归的方式对每一个未访问的节点进行探索,直到找到所有可达节点。
阅读全文