c++dfs算法

深度优先搜索（DFS）是一种常用的图遍历算法，它通过递归或者栈来实现。在C++中可以使用递归方法来实现DFS算法。 以下是一个使用C++实现DFS的简单例子： #include #include using namespace std; vector> graph; vector visited; void dfs(int node) { visited[node] = true; cout « node « " “; for (int i = 0; i < graph[node].size(); i++) { int neighbor = graph[node][i]; if (!visited[neighbor]) { dfs(neighbor); } } } int main() { int n = 5; // 图中节点的个数 // 初始化图的邻接表 graph.resize(n); graph[0] = {1, 2}; graph[1] = {0, 2, 3}; graph[2] = {0, 1, 4}; graph[3] = {1}; graph[4] = {2}; visited.assign(n, false); cout « “DFS traversal starting from node 0: “; dfs(0); return 0; } 在这个例子中，我们首先定义了一个图的邻接表 graph 和一个记录节点访问状态的数组 visited。然后我们实现了一个递归的DFS函数 dfs，它从给定的起始节点开始遍历整个图。最后在主函数中我们初始化了一个简单的无向图，并从节点0开始进行DFS遍历。 运行这段代码，会输出从节点0开始的DFS遍历结果。 需要注意的是，DFS在处理大规模图时可能会面临栈溢出的问题，因此在实际应用中可能需要对递归深度进行一定的限制或使用非递归的实现方式。