首页dfs和bfs算法c++模板

dfs和bfs算法c++模板

时间: 2025-01-17 14:02:53 浏览: 61

### C++ 中的 DFS 和 BFS 算法实现 #### 深度优先搜索 (DFS) 深度优先搜索是一种用于遍历或搜索树或图的算法。该方法会尽可能深地探索子节点，直到无法继续为止。 ```cpp #include <iostream> #include <vector> using namespace std; void dfs(int node, vector<bool>& visited, const vector<vector<int>>& graph) { if (visited[node]) return; cout << "Visit Node: " << node << endl; // 访问当前结点 visited[node] = true; for (int neighbor : graph[node]) { // 遍历相邻结点 dfs(neighbor, visited, graph); // 对未访问过的邻居执行递归调用 } } ``` 此代码片段展示了如何通过递归来实现深度优先搜索[^1]。 #### 广度优先搜索 (BFS) 广度优先搜索也是一种用于遍历或搜索树或图的方法。它按照层次顺序逐层扩展节点，通常借助队列来管理待处理的节点列表。 ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; void bfs(int startNode, vector<bool>& visited, const vector<vector<int>>& graph) { queue<int> q; q.push(startNode); visited[startNode] = true; while (!q.empty()) { int currentNode = q.front(); q.pop(); cout << "Visit Node: " << currentNode << endl; // 处理当前结点 for (int neighbor : graph[currentNode]) { // 将所有邻接但尚未被标记为已访问的顶点加入到队列中 if (!visited[neighbor]) { q.push(neighbor); visited[neighbor] = true; } } } } ``` 这段程序说明了利用队列结构来进行广度优先遍历的过程[^2]。对于上述两种算法，在实际应用之前还需要初始化 `graph` 变量以及设置初始状态下的 `visited` 数组。此外，根据具体应用场景的不同可能还需调整输入输出部分以适应特定需求。

阅读全文