01.00_搜索
搜索
深度优先搜索 (DFS)
深度优先搜索是一种优先走到最深的搜索算法。
特点
- 空间复杂度：
，其中h为搜索树深度
- 时间复杂度：
，其中b为分支因子，d为深度
- 适用于求解所有可能的解或最优解
分类
| 普通DFS | 无优化的深搜 | 排列、组合、子集 |
| 剪枝DFS | 带优化的深搜 | 八皇后、数独、迷宫 |
| 记忆化DFS | 状态记录的深搜 | 动态规划相关问题 |
| 双向DFS | 从起点和终点同时搜索 | 最短路径、状态转换 |
广度优先搜索 (BFS)
广度优先搜索是一种层层推进的搜索算法。
特点
- 空间复杂度：
- 时间复杂度：
- 适用于求解最短路径或最少步数
分类
| 普通BFS | 无权图最短路 | 迷宫最短路、单词接龙 |
| 双向BFS | 从起点和终点同时搜索 | 大规模状态空间搜索 |
| 启发式BFS | 带评估函数的BFS | A*算法、最优路径搜索 |
| 多源BFS | 多个起点同时BFS | 多源最短路、病毒传播 |
应用场景对比
DFS适合：
- 求解所有可能的解
- 内存空间受限
- 搜索树较深的情况
BFS适合：
- 求解最短路径
- 求解最少步数
- 层次遍历问题
选择建议
- 如果需要找到所有解，选择DFS
- 如果需要找最短路径，选择BFS
- 如果状态空间巨大，考虑使用剪枝或双向搜索
- 如果有明确的评估函数，考虑启发式搜索
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
投递腾讯等公司6个岗位 >
滴滴公司福利 694人发布
