vector 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** 主要应用于最短路径计算场景下，尤其是无权图中的单源最短路径问题。 两者均依赖于图的数据结构形式（如邻接矩阵或邻接列表），实际应用需根据具体需求调整设计。

<think>好的，我现在需要回答用户关于C++中DFS和BFS的实现和用法的问题。首先，我要确认用户的需求。用户可能是在学习图算法，想要具体的代码示例以及应用场景的解释。我需要先回顾DFS和BFS的基本概念，然后考虑在C++中如何实现这两种算法，同时举出常见的应用场景。 首先，DFS（深度优先搜索）通常用递归或者栈来实现，适用于路径查找、连通性检测等问题。而BFS（广度优先搜索）则用队列实现，适合最短路径问题、层次遍历等。接下来，我需要给出这两种算法的基本实现代码，可能需要用邻接表或邻接矩阵来表示图结构。用户可能需要具体的示例代码，所以应该提供一个简单但完整的例子，比如使用邻接表，并展示如何遍历节点。 然后，要考虑应用场景部分。比如DFS用于拓扑排序、检测环路，BFS用于社交网络中的最短连接查找，或者迷宫的最短路径。这些例子能帮助用户理解何时选择哪种算法。 另外，用户提到的引用中有关于图算法的资料，比如Dijkstra算法，但用户的问题是关于DFS和BFS，所以可能需要简要提到它们的区别，但重点放在实现和用法上。同时要确保代码语法正确，符合C++标准，比如使用STL的vector、queue、stack等容器。 在结构上，应该先分别介绍DFS和BFS，给出实现代码，再讨论它们的应用场景，最后回答相关问题。需要检查代码是否有误，比如递归终止条件是否正确，是否处理了访问过的节点，避免死循环。比如在DFS中，使用一个visited数组来记录已访问的节点，防止重复访问。 可能还需要比较两种算法的时间复杂度和空间复杂度，但用户的问题主要是实现和用法，所以这部分可能放在相关问题里。另外，用户要求生成相关问题，我需要考虑常见的疑问，比如复杂度、优化方法、具体应用案例等。 最后，确保引用正确，用户提供的引用中有关于图算法的介绍，可以引用[^3]提到图算法，比如Dijkstra，但可能不直接相关，所以只在适当的地方引用。同时，代码部分要使用正确的格式，用反引号包裹，并标明语言类型。 总结步骤： 1. 定义DFS和BFS的基本概念。 2. 提供C++代码示例，使用邻接表表示图。 3. 分别展示DFS（递归和栈）和BFS（队列）的实现。 4. 讨论应用场景，举实际例子。 5. 列出相关问题，如复杂度、优化、比较等。 6. 检查引用是否正确，代码是否正确无误。</think>### C++中DFS与BFS的实现与用法 #### 1. DFS（深度优先搜索） **概念**：DFS通过递归或栈实现，优先深入访问未探索的分支，适合解决路径探索、连通性判断等问题。 **代码实现**（邻接表表示图）： ```cpp #include <iostream> #include <vector> #include <stack> using namespace std; void dfsRecursive(int node, vector<bool>& visited, const vector<vector<int>>& graph) { visited[node] = true; cout << node << " "; // 处理当前节点 for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfsRecursive(neighbor, visited, graph); } } } void dfsStack(int start, const vector<vector<int>>& graph) { stack<int> s; vector<bool> visited(graph.size(), false); s.push(start); visited[start] = true; while (!s.empty()) { int node = s.top(); s.pop(); cout << node << " "; // 处理当前节点 // 反向遍历邻接节点以保证顺序一致 for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) { if (!visited[*it]) { s.push(*it); visited[*it] = true; } } } } ``` **应用场景**： - 拓扑排序（如任务调度依赖分析） - 检测图中环路（如编译器死锁检测） - 连通分量标记（图像处理中的区域填充） --- #### 2. BFS（广度优先搜索） **概念**：BFS通过队列实现，按层次遍历节点，适合求解最短路径、社交网络关系扩散等问题。 **代码实现**： ```cpp #include <queue> void bfs(int start, const vector<vector<int>>& graph) { queue<int> q; vector<bool> visited(graph.size(), false); q.push(start); visited[start] = true; while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; // 处理当前节点 for (int neighbor : graph[node]) { if (!visited[neighbor]) { q.push(neighbor); visited[neighbor] = true; } } } } ``` **应用场景**： - 无权图最短路径（如迷宫最短出口） - 社交网络中的“六度分隔”理论验证 - 网络爬虫的页面抓取策略 --- #### 3. 完整示例（以图的遍历为例） **图的构建与调用**： ```cpp int main() { // 邻接表表示图：节点0~3 vector<vector<int>> graph = { {1, 2}, // 节点0的邻居 {2}, // 节点1的邻居 {0, 3}, // 节点2的邻居 {3} // 节点3的邻居 }; cout << "DFS递归实现: "; vector<bool> visited1(4, false); dfsRecursive(0, visited1, graph); // 输出: 0 1 2 3 cout << "\nDFS栈实现: "; dfsStack(0, graph); // 输出: 0 2 3 1 cout << "\nBFS实现: "; bfs(0, graph); // 输出: 0 1 2 3 return 0; } ``` ---