首页C++的BFS和DFS

C++的BFS和DFS

时间: 2025-01-05 10:31:18 浏览: 46

### C++ 中 BFS 和 DFS 的实现与应用 #### 广度优先搜索 (BFS) 广度优先搜索是一种逐层扩展节点的算法，适合用于求解最短路径和层次遍历等问题[^1]。 ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; void bfs(int start, vector<vector<int>>& adjList, int n) { queue<int> q; vector<bool> visited(n, false); q.push(start); visited[start] = true; while (!q.empty()) { int node = q.front(); cout << "Visited: " << node << endl; q.pop(); for (int neighbor : adjList[node]) { if (!visited[neighbor]) { q.push(neighbor); visited[neighbor] = true; } } } } ``` 这段代码展示了如何利用队列来管理待访问节点，并按层次顺序进行访问。每次处理当前节点后，将其未被访问过的邻居加入队列等待后续处理[^2]。 #### 深度优先搜索 (DFS) 深度优先搜索则倾向于尽可能深地进入子树中去寻找目标，在遇到死胡同时再回溯返回上一层继续探索其他分支。这种方法对于那些需要深入挖掘可能性空间的问题特别有用。 ```cpp #include <iostream> #include <vector> using namespace std; void dfs(int node, const vector<vector<int>>& adjList, vector<bool>& visited) { cout << "Visited: " << node << endl; visited[node] = true; for (int neighbor : adjList[node]) { if (!visited[neighbor]) { dfs(neighbor, adjList, visited); } } } // 调用示例 /* int main() { // 假设已经定义好了adjList和n... vector<bool> visited(n, false); for (int i = 0; i < n; ++i) { if (!visited[i]) { dfs(i, adjList, visited); } } return 0; }*/ ``` 这里展示了一个递归版本的DFS函数，它会先标记并打印当前正在访问的顶点，然后再依次对其所有尚未访问过的孩子调用自己来进行进一步查找操作[^3]。

阅读全文