DFS与BFS模块总结
DFS（深度优先搜索）和 BFS（广度优先搜索）是图和树遍历中的核心算法，其实现涉及多个关键模块。以下从 数据结构、核心逻辑、辅助功能、优化技术 四个维度对两者涉及的模块进行总结对比：
一、数据结构模块
| 模块 | DFS 实现方式 | BFS 实现方式 |
|---|---|---|
| 主存储结构 | 栈（Stack） 递归调用隐式使用系统栈 显式实现时用 stack 容器 | 队列（Queue） 使用 queue 容器（FIFO 顺序） |
| 访问记录 | 哈希表/数组 记录已访问节点（避免重复访问和循环） | 同 DFS，需记录已访问节点 |
| 路径存储 | 可选链表/数组 回溯时记录当前路径（如迷宫问题） | 可选父节点指针 重建最短路径时需记录前驱节点 |
二、核心逻辑模块
1. 初始化
- DFS：
- 将起始节点压入栈（或递归调用）。
- 标记起始节点为已访问。
- BFS：
- 将起始节点入队。
- 标记起始节点为已访问。
2. 遍历循环
- DFS：
while 栈不为空:弹出栈顶节点 ufor 邻接节点 v of u:if v 未访问:标记 v 为已访问将 v 压入栈（可选：处理节点 v）BFS：
while 队列不为空:出队节点 ufor 邻接节点 v of u:if v 未访问:标记 v 为已访问将 v 入队（可选：记录父节点或距离）3. 终止条件
- 两者均在主存储结构（栈/队列）为空时终止。
三、辅助功能模块
| 功能 | DFS 实现 | BFS 实现 |
|---|---|---|
| 路径重建 | 需显式维护路径（如通过递归回溯或栈记录） | 通过父节点指针反向追溯路径 |
| 层级信息 | 需额外计数器或递归深度参数 | 天然支持层级遍历（如二叉树按层输出） |
| 最短路径 | 不保证最短路径（除非无权图且回溯时记录） | 保证无权图最短路径（通过队列的 FIFO 特性） |
| 连通性检测 | 通过一次遍历标记所有可达节点 | 同 DFS，但 BFS 更直观显示层级关系 |
四、优化技术模块
1. 通用优化
- 剪枝：提前终止无效分支（如搜索到目标后停止）。
- 双向搜索：结合 DFS 和 BFS（如双向 BFS 优化最短路径）。
- 迭代加深（IDS）：结合 DFS 的空间优势和 BFS 的完备性（用于状态空间搜索）。
2. DFS 专属优化
- 回溯法：通过递归和状态重置高效解决组合问题（如八皇后、子集生成）。
- Tarjan 算法：利用 DFS 树检测强连通分量（SCC）。
- 记忆化：缓存已计算结果（如动态规划中的递归转迭代）。
3. BFS 专属优化
- 0-1 BFS：使用双端队列优化边权为 0 或 1 的图的最短路径（如 Dijkstra 特例）。
- *A 算法**：结合启发式函数优化 BFS 的搜索方向（如路径规划）。
- 并行 BFS：分层并行处理队列中的节点（适用于大规模图）。
五、模块对比总结
| 模块 | DFS 特点 | BFS 特点 |
|---|---|---|
| 数据结构 | 依赖栈，适合深度优先探索 | 依赖队列，适合广度优先扩展 |
| 路径处理 | 需显式回溯或栈记录路径 | 通过父节点指针隐式记录路径 |
| 空间效率 | 适合深度大、宽度小的结构（如长链） | 适合宽度大、深度小的结构（如宽树） |
| 优化方向 | 回溯、剪枝、递归转迭代 | 层级优化、启发式搜索、并行化 |
六、典型应用场景
- DFS：
- 组合问题（子集、排列）
- 连通性检测（如无向图的连通块）
- 拓扑排序（有向无环图）
- 回溯算法（数独、N 皇后）
- BFS：
- 最短路径（无权图或边权相同）
- 层级遍历（二叉树层序输出）
- 社交网络中的“几度好友”查询
- 迷宫问题的最少步数解