图的深度优先搜索(DFS)遍历算法详解与C++实现

"图的深度优先搜索(DFS)遍历算法详解与C++实现"\n\n本文详细讲解了图的深度优先搜索(DFS)遍历算法，并提供了C++代码实现。通过图文并茂的方式，阐述了DFS算法的原理和步骤，并以示例代码演示了如何使用C++语言实现DFS遍历。\n\n## 图的深度优先搜索(DFS)算法\n深度优先搜索(Depth-First Search, DFS) 是一种用于遍历或搜索树或图数据结构的算法。它从起点开始，沿着一条路径一直向下搜索，直到到达一个叶节点或已经访问过的节点。然后，它回溯到上一个节点，继续搜索其他未访问过的路径。\n\n## DFS算法的步骤\n1. 从起点开始，访问起点，并将起点标记为已访问。\n2. 找到起点的一个未访问的邻接节点，并将该节点标记为已访问。\n3. 从该邻接节点开始，重复步骤2，直到所有与该节点相连的节点都被访问。\n4. 如果所有与当前节点相连的节点都被访问，则回溯到上一个节点，继续搜索其他未访问的路径。\n5. 重复步骤2-4，直到所有节点都被访问。\n\n## C++代码实现\nc++\n#include <iostream>\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nvoid dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {\n visited[node] = true;\n cout << node << " ";\n for (int i = 0; i < graph[node].size(); i++) {\n int neighbor = graph[node][i];\n if (!visited[neighbor]) {\n dfs(graph, visited, neighbor);\n }\n }\n}\n\nint main() {\n int n, e;\n cin >> n >> e;\n \n vector<vector<int>> graph(n+1);\n vector<bool> visited(n+1, false);\n \n for (int i = 0; i < e; i++) {\n int x, y;\n cin >> x >> y;\n graph[x].push_back(y);\n graph[y].push_back(x);\n }\n \n for (int i = 1; i <= n; i++) {\n sort(graph[i].begin(), graph[i].end());\n }\n \n dfs(graph, visited, 1);\n \n return 0;\n}\n\n\n## 代码说明\n1. graph 是一个二维向量，用于存储图的邻接表表示。\n2. visited 是一个布尔向量，用于记录每个节点是否被访问。\n3. dfs 函数是深度优先搜索的核心函数，它递归地遍历图。\n4. main 函数从输入中读取图的信息，并调用 dfs 函数进行遍历。\n\n## 总结\n深度优先搜索(DFS)算法是一种常用的图遍历算法，它能够有效地探索图的连通性。本文详细讲解了DFS算法的原理和步骤，并提供了C++代码实现，希望能够帮助读者更好地理解和应用DFS算法。\n