在 C++ 中，深度优先搜索（DFS）和广度优先搜索（BFS）是两种重要的图和树的遍历算法，下面为你详细总结这两种算法。
深度优先搜索（DFS）
基本概念
深度优先搜索是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。
实现思路
- 递归实现：通过递归函数不断深入子节点进行搜索，直到无法继续深入，然后回溯。
- 栈实现：使用栈来模拟递归调用的过程，将待访问的节点压入栈中，每次从栈中取出一个节点进行访问，并将其未访问的子节点压入栈中。
代码示例（递归实现，以图的遍历为例）
#include <iostream>
#include <vector>using namespace std;// 定义图的邻接表表示
vector<vector<int>> graph;
// 标记节点是否被访问过
vector<bool> visited;// 深度优先搜索函数
void dfs(int node) {visited[node] = true;cout << node << " ";// 遍历当前节点的所有邻接节点for (int neighbor : graph[node]) {if (!visited[neighbor]) {dfs(neighbor);}}
}int main() {int n = 5; // 节点数量graph.resize(n);visited.resize(n, false);// 添加边graph[0].push_back(1);graph[0].push_back(2);graph[1].push_back(3);graph[2].push_back(4);// 从节点 0 开始进行深度优先搜索dfs(0);return 0;
}
复杂度分析
- 时间复杂度：O(V+E)，其中 V是节点数，E是边数。因为每个节点和每条边都需要被访问一次。
- 空间复杂度：O(V)，主要用于递归调用栈的空间，最坏情况下需要存储所有节点。
应用场景
连通性问题：判断图中两个节点是否连通。
路径搜索：寻找从一个节点到另一个节点的路径。
拓扑排序：对有向无环图进行拓扑排序。
广度优先搜索（BFS）
基本概念
广度优先搜索是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
实现思路
使用队列来实现，将起始节点加入队列，然后不断从队列中取出节点进行访问，并将其未访问的子节点加入队列。
代码示例（以图的遍历为例）
#include <iostream>
#include <vector>
#include <queue>using namespace std;// 定义图的邻接表表示
vector<vector<int>> graph;
// 标记节点是否被访问过
vector<bool> visited;// 广度优先搜索函数
void bfs(int start) {queue<int> q;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;}}}
}int main() {int n = 5; // 节点数量graph.resize(n);visited.resize(n, false);// 添加边graph[0].push_back(1);graph[0].push_back(2);graph[1].push_back(3);graph[2].push_back(4);// 从节点 0 开始进行广度优先搜索bfs(0);return 0;
}
复杂度分析
- 时间复杂度：O(V+E)，其中 V 是节点数，E是边数。因为每个节点和每条边都需要被访问一次。
- 空间复杂度：O(V)，主要用于队列的空间，最坏情况下需要存储所有节点。
应用场景
- 最短路径问题：在无权图中寻找从一个节点到另一个节点的最短路径。
- 层次遍历：按层次遍历树或图。
- 连通分量：找出图中的所有连通分量。
两者对比
- 搜索顺序：DFS 优先深入探索，BFS 优先广度扩展。
- 空间复杂度：DFS 主要依赖递归栈，空间复杂度可能较高；BFS 主要依赖队列，空间复杂度相对稳定。
- 应用场景：DFS 适合寻找路径、连通性问题等；BFS 适合最短路径问题、层次遍历等。