广度优先搜索（BFS） vs 深度优先搜索（DFS）：算法对比与 C++ 实现

一、BFS 和 DFS 的核心思想

1. BFS（广度优先搜索）

2. DFS（深度优先搜索）

二、BFS 和 DFS 的对比

三、C++ 代码实现

1. BFS 实现（邻接表表示的无向图）

2. DFS 实现（递归与迭代两种方式）

四、关键细节说明

1. BFS 的关键点

2. DFS 的关键点

五、应用场景对比

六、总结

一、BFS 和 DFS 的核心思想

1. BFS（广度优先搜索）

核心思想：按“层级”逐层遍历，先访问离起点最近的节点，再逐步向外扩散。
类比：类似水波扩散，一层一层向外推进。
数据结构：队列（FIFO）。
适用场景：最短路径（未加权图）、社交网络层级关系、迷宫最短路径。

2. DFS（深度优先搜索）

核心思想：沿着一条路径尽可能深入，直到无法继续时回溯，尝试其他分支。
类比：走迷宫时，遇到岔路选择一条路走到头，再返回选择其他路。
数据结构：栈（LIFO）或递归调用栈。
适用场景：拓扑排序、连通性检测、回溯问题（如八皇后）、图的环路检测。

二、BFS 和 DFS 的对比

特性	BFS	DFS
遍历顺序	层级遍历（近到远）	深度优先（一条路走到黑）
数据结构	队列（先进先出）	栈（后进先出）或递归
空间复杂度	O(N)（最坏情况，如完全二叉树）	O(H)（H为树的高度，平衡树时为 O(logN)）
时间复杂度	O(N + E)（N为节点数，E为边数）	同左
最短路径	天然支持（未加权图）	需额外处理（如记录路径长度）
内存消耗	较高（存储每一层节点）	较低（仅存储当前路径）
实现复杂度	简单（固定队列操作）	递归简单，迭代需显式栈

三、C++ 代码实现

1. BFS 实现（邻接表表示的无向图）

#include <iostream>
#include <queue>
#include <vector>
using namespace std;void bfs(const vector<vector<int>>& graph, int start) {vector<bool> visited(graph.size(), false);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]) {visited[neighbor] = true;q.push(neighbor);}}}
}// 示例图结构
vector<vector<int>> graph = {{1, 2},     // 节点0的邻居{0, 3, 4},  // 节点1的邻居{0, 5, 6},  // 节点2的邻居{1},        // 节点3的邻居{1},        // 节点4的邻居{2},        // 节点5的邻居{2}         // 节点6的邻居
};int main() {cout << "BFS遍历结果: ";bfs(graph, 0); // 输出: 0 1 2 3 4 5 6return 0;
}

2. DFS 实现（递归与迭代两种方式）

// 递归实现
void dfsRecursive(const vector<vector<int>>& graph, int node, vector<bool>& visited) {visited[node] = true;cout << node << " "; // 访问节点for (int neighbor : graph[node]) {if (!visited[neighbor]) {dfsRecursive(graph, neighbor, visited);}}
}// 迭代实现（显式栈）
void dfsIterative(const vector<vector<int>>& graph, int start) {vector<bool> visited(graph.size(), false);stack<int> s;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]) {visited[*it] = true;s.push(*it);}}}
}int main() {cout << "DFS递归遍历结果: ";vector<bool> visited(graph.size(), false);dfsRecursive(graph, 0, visited); // 输出: 0 1 3 4 2 5 6cout << "\nDFS迭代遍历结果: ";dfsIterative(graph, 0);          // 输出: 0 1 3 4 2 5 6return 0;
}

四、关键细节说明

1. BFS 的关键点

队列操作：每次从队头取出节点，并将未访问的邻居加入队尾。
最短路径：BFS 首次访问到目标节点时，路径一定是最短的（适用于未加权图）。
空间复杂度：最坏情况下需存储所有节点（如完全二叉树最后一层）。

2. DFS 的关键点

递归与栈：递归隐式使用系统栈，迭代显式使用栈。
遍历顺序：迭代实现中，若按正序访问邻居，结果可能与递归顺序不同（需反向遍历邻居）。
应用场景：适合探索所有可能性（如回溯问题），但可能陷入深层分支无法及时返回。

五、应用场景对比

问题类型	推荐算法	原因
未加权图最短路径	BFS	天然支持最短路径
图的连通性检测	DFS/BFS	二者均可快速遍历所有连通节点
拓扑排序	DFS	天然支持后序遍历的逆序
迷宫所有路径	DFS	回溯特性适合探索所有可能路径
社交网络层级关系分析	BFS	按层遍历符合实际场景
检测环路	DFS	通过回溯标记路径，容易检测重复访问