bfs,dfs区别
2024-10-12 18:10:21
一般来说用DFS解决的问题都可以用BFS来解决。
DFS(深搜的同时考虑回溯）
bfs＝队列，入队列，出队列；dfs=栈，压栈，出栈
bfs是按一层一层来访问的，所以适合有目标求最短路的步数，你想想层层搜索每次层就代表了一步。bfs优先访问的是兄弟节点，只有这一层全部访问完才能访问下一层，也就是说bfs第几层就代表当前可以走到的位置(结点).而dfs是按递归来实现的，它优先搜索深度，再回溯，优先访问的是没有访问过的子节点
DFS多用于连通性问题因为其运行思想与人脑的思维很相似，故解决连通性问题更自然。BFS多用于解决最短路问题，其运行过程中需要储存每一层的信息，所以其运行时需要储存的信息量较大，如果人脑也可储存大量信息的话，理论上人脑也可运行BFS。
总的来说多数情况下运行BFS所需的内存会大于DFS需要的内存(DFS一次访问一条路，BFS一次访问多条路)，DFS容易爆栈(栈不易"控制")，BFS通过控制队列可以很好解决"爆队列"风险。
它们两者间各自的优势需要通过实际的问题来具体分析，根据它们各自的特点来应用于不同的问题中才能获得最优的性能。
总的来说多数情况下运行BFS所需的内存会大于DFS需要的内存(DFS一次访问一条路，BFS一次访问多条路)，DFS容易爆栈(栈不易"控制")，BFS通过控制队列可以很好解决"爆队列"风险。
它们两者间各自的优势需要通过实际的问题来具体分析，根据它们各自的特点来应用于不同的问题中才能获得最优的性能。
最新文章
- java中获取接口（方法）中的参数名字(eclipse设置编译参数)（java8 javac -parameters）
- The Rotation Game（IDA*算法）
- September 27th 2016 Week 40th Tuesday
- Eclipse导出可执行Jar文件（包含第三方Jar包）
- poj 2192 (DP)
- redis 在windows上运行
- java设计模式--行为型模式--迭代模式
- adb 卸载android系统程序
- Android NDK and OpenCV Development With Android Studio
- 人工智能一：Al学习路线
- springboot测试、打包、部署
- 1python简介
- Java的hashCode和equals方法
- Linux的JDK配置
- POJ2061 Subsequence 2017-05-25 19:49 83人阅读 评论(0) 收藏
- 『编程题全队』Alpha阶段事后诸葛亮分析
- 促使团队紧密协作[高效能程序员的修炼-N1]
- Eclipse cdt debug时‘Error while launching command: gdb.exe --version’
- 【C#高级编程】笔记之核心C#
- IOS版微信小视频导出方法