BFS vs DFS
概述
广度优先搜索（BFS, Breadth-First Search）和深度优先搜索（DFS, Depth-First Search）是图遍历的两种基本算法。BFS 使用队列，按层序逐层扩展，天然适合求最短路径；DFS 使用栈（或递归），沿一条路径深入到底再回溯，天然适合检测环和拓扑排序。二者时间复杂度相同，均为 。
定义
BFS（广度优先搜索）
从起始顶点出发，先访问所有距离为 1 的邻居，再访问所有距离为 2 的邻居，依此类推。使用队列（FIFO）管理待访问顶点，保证按距离递增的顺序遍历。在无权图中，BFS 天然求出从起点到所有其他顶点的最短路径。
DFS（深度优先搜索）
从起始顶点出发，沿一条路径尽可能深入，到达死端后回溯到最近的分叉点继续探索。使用栈（LIFO）或递归调用管理待访问顶点，保证沿深度方向优先遍历。DFS 天然适合检测有向图中的环和生成拓扑排序。
对比维度
| 维度 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列（FIFO） | 栈（LIFO）或递归 |
| 遍历策略 | 层序扩展，逐层访问 | 深度优先，深入到底再回溯 |
| 最短路径 | 无权图中天然求最短路径 | 不保证最短路径 |
| 空间复杂度 | （队列最多存 个顶点） | （递归栈深度最大为 ） |
| 时间复杂度 | ||
| 典型应用 | 最短路径、层序遍历、社交网络 | 拓扑排序、环检测、连通分量、迷宫 |
| 实现方式 | 迭代（队列） | 递归或迭代（栈） |
| 遍历结果 | BFS 树 | DFS 树/森林 |
| 记忆化 | visited 数组避免重复访问 | visited 数组避免重复访问 |
| 环检测 | 需要额外处理 | 天然支持（回边检测） |
关键区别
- BFS 按层扩展，先访问近的顶点；DFS 沿深度深入，先走到底再回溯
- BFS 在无权图中能找到最短路径（因为按距离递增访问），DFS 不能
- DFS 天然适合检测有向图中的环（遇到已访问且未回溯完成的顶点即有环），BFS 需要额外处理
- DFS 是拓扑排序的基础算法，BFS 也可实现拓扑排序（Kahn 算法），但思路不同
- BFS 的队列实现天然是迭代的，DFS 的递归实现更简洁但可能栈溢出
联系
- 二者都是连通图的遍历算法，时间复杂度相同
- BFS 和 DFS 都能检测图的连通性、找出所有连通分量
- BFS 树和 DFS 树都是原图的生成树（或生成森林）
- 二者都需要 visited 数组来避免重复访问，防止无限循环
- 在实际应用中，选择 BFS 还是 DFS 取决于问题需求：求最短路径用 BFS，求拓扑排序或检测环用 DFS