BFS和DFSc++模板

<think>好的，用户需要C++实现的BFS和DFS算法模板，并希望有示例代码。首先，我需要回忆BFS和DFS的基本原理。BFS使用队列，逐层访问节点；而DFS则用栈或递归，深入到底再回溯。然后，根据用户提供的引用资料，特别是引用1、2、3、4，这些资料详细说明了实现时的注意事项，比如队列和栈的使用，如何避免重复访问，以及特殊情况处理。 接下来，我需要确保代码符合C++标准，并正确使用STL容器，比如队列和栈。对于BFS，通常会使用邻接表或邻接矩阵来表示图结构。需要维护一个访问数组，记录已访问的节点，防止死循环。DFS的实现可以用递归或者显式栈，这里可能需要两种实现方式。 用户可能还需要了解两种算法的应用场景和优缺点，比如BFS适合最短路径问题，DFS适合拓扑排序或连通性问题。同时，要注意代码中的注释和可读性，方便用户理解。 然后，检查是否有遗漏的细节，比如处理图为空的情况，或者在遍历邻接节点时的循环逻辑是否正确。还要确保引用的正确性，比如引用1提到使用队列和栈，引用4提到DFS的空间复杂度等。 最后，生成相关问题，帮助用户进一步学习，比如比较BFS和DFS的区别，或者如何处理图中的环。确保所有内容结构清晰，符合用户的要求。</think>### C++ BFS与DFS算法模板实现 #### 1. BFS算法模板（广度优先搜索） **实现原理**：基于队列实现，逐层遍历所有相邻节点[^3][^4] ```cpp #include <queue> #include <vector> using namespace std; void bfs(vector<vector<int>>& graph, int start) { int n = graph.size(); vector<bool> visited(n, false); queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int node = q.front(); q.pop(); // 处理当前节点 for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } ``` #### 2. DFS算法模板（深度优先搜索） **实现原理**：基于递归或栈实现，深度优先遍历[^2] **递归实现**： ```cpp #include <vector> using namespace std; void dfs_recursive(vector<vector<int>>& graph, vector<bool>& visited, int node) { visited[node] = true; // 处理当前节点 for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs_recursive(graph, visited, neighbor); } } } // 调用入口 void dfs(vector<vector<int>>& graph, int start) { vector<bool> visited(graph.size(), false); dfs_recursive(graph, visited, start); } ``` **栈实现**： ```cpp #include <stack> #include <vector> using namespace std; void dfs_stack(vector<vector<int>>& graph, int start) { int n = graph.size(); vector<bool> visited(n, false); stack<int> s; s.push(start); visited[start] = true; while (!s.empty()) { int node = s.top(); s.pop(); // 处理当前节点 for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; s.push(neighbor); } } } } ``` ### 算法说明 1. **数据结构选择**： - BFS使用$O(V)$队列空间 - DFS递归版本使用$O(V)$递归栈空间，栈实现版本空间复杂度相同 2. **注意事项**： - 必须维护`visited`数组防止重复访问 - 邻接表存储时时间复杂度为$O(V+E)$ - 处理起始节点的访问标记应在入队/入栈时设置[^1] 3. **应用场景对比**： | 特性 | BFS | DFS | |-------------|----------------------|----------------------| | 数据结构 | 队列 | 栈/递归 | | 空间复杂度 | $O(V)$ | $O(V)$ | | 适用场景 | 最短路径、层级遍历 | 拓扑排序、连通性检测 |