C++ dfs bfs

### C++ 中的 DFS 和 BFS 实现 在图遍历算法中，深度优先搜索 (DFS) 和广度优先搜索 (BFS) 是两种基本方法。以下是它们的具体实现以及解释。 #### 深度优先搜索 (DFS) DFS 使用栈结构来记录访问路径，默认情况下可以通过递归来实现。下面是一个基于邻接表表示的图的 DFS 示例： ```cpp #include <iostream> #include <vector> using namespace std; void dfs(int node, vector<vector<int>> &adjList, vector<bool> &visited) { visited[node] = true; // 标记当前节点已访问 cout << node << " "; // 输出当前节点 for (int neighbor : adjList[node]) { // 遍历邻居节点 if (!visited[neighbor]) { // 如果邻居未被访问 dfs(neighbor, adjList, visited); // 对邻居执行 DFS } } } int main() { int n = 5; // 节点数 vector<vector<int>> adjList(n); // 添加边 adjList[0].push_back(1); adjList[0].push_back(2); adjList[1].push_back(2); adjList[2].push_back(0); adjList[2].push_back(3); adjList[3].push_back(3); vector<bool> visited(n, false); // 初始化所有节点为未访问状态 cout << "Depth First Traversal (starting from vertex 2): "; dfs(2, adjList, visited); // 开始 DFS 遍历 } ``` 上述代码展示了如何通过递归方式实现 DFS[^4]。 #### 广度优先搜索 (BFS) BFS 利用队列数据结构按层次顺序访问节点。下面是基于邻接表的 BFS 实现： ```cpp #include <iostream> #include <vector> #include <queue> using namespace std; void bfs(int startNode, vector<vector<int>> &adjList, vector<bool> &visited) { queue<int> q; visited[startNode] = true; // 标记起始节点已访问 q.push(startNode); // 将起始节点加入队列 while (!q.empty()) { // 当队列不为空时继续处理 int currentNode = q.front(); // 获取队首元素 q.pop(); cout << currentNode << " "; // 输出当前节点 for (int neighbor : adjList[currentNode]) { // 遍历邻居节点 if (!visited[neighbor]) { // 如果邻居未被访问 visited[neighbor] = true; // 标记邻居为已访问 q.push(neighbor); // 加入队列等待后续处理 } } } } int main() { int n = 5; // 节点数 vector<vector<int>> adjList(n); // 添加边 adjList[0].push_back(1); adjList[0].push_back(2); adjList[1].push_back(2); adjList[2].push_back(0); adjList[2].push_back(3); adjList[3].push_back(3); vector<bool> visited(n, false); // 初始化所有节点为未访问状态 cout << "Breadth First Traversal (starting from vertex 2): "; bfs(2, adjList, visited); // 开始 BFS 遍历 } ``` 此代码片段演示了利用队列完成 BFS 的过程[^5]。 #### 总结 - **DFS** 更适合用于寻找连通分量或者检测环等问题。 - **BFS** 主要应用于最短路径计算场景下，尤其是无权图中的单源最短路径问题。 两者均依赖于图的数据结构形式（如邻接矩阵或邻接列表），实际应用需根据具体需求调整设计。