BFS与DFS区别和特点
2024-10-21 15:54:43
什么时候用DFS，什么时候用BFS?(DFS和BFS的特点和异同)
二维数组的题目，N小于20的，适用DFS。而一般 N<= 200，N<=1000这种，一定不可能用DFS去做。而且并不只是整个题目不能用DFS，其中的每一步也不能使用DFS。
BFS的基本步骤
1.将初始点（一个或多个）加入一个集合尾
2.从集合头取出点，判断初始点的周边点，将符合条件的点加入队列
3.重复2操作，直至集合为空。(一般每个点只加入队列一次)
一般来说用DFS解决的问题都可以用BFS来解决。
DFS(深搜的同时考虑回溯）
bfs＝队列，入队列，出队列；dfs=栈，压栈，出栈
bfs是按一层一层来访问的，所以适合有目标求最短路的步数，你想想层层搜索每次层就代表了一步。bfs优先访问的是兄弟节点，只有这一层全部访问完才能访问下一层，也就是说bfs第几层就代表当前可以走到的位置(结点).而dfs是按递归来实现的，它优先搜索深度，再回溯，优先访问的是没有访问过的子节点
DFS多用于连通性问题因为其运行思想与人脑的思维很相似，故解决连通性问题更自然。BFS多用于解决最短路问题，其运行过程中需要储存每一层的信息，所以其运行时需要储存的信息量较大，如果人脑也可储存大量信息的话，理论上人脑也可运行BFS。
总的来说多数情况下运行BFS所需的内存会大于DFS需要的内存(DFS一次访问一条路，BFS一次访问多条路)，DFS容易爆栈(栈不易"控制")，BFS通过控制队列可以很好解决"爆队列"风险。
它们两者间各自的优势需要通过实际的问题来具体分析，根据它们各自的特点来应用于不同的问题中才能获得最优的性能。
最新文章
- SDRAM的主要参数
- 二、JavaScript语言--JS实践--信息滚动效果制作
- Concurrent Assertion
- (Array) 一个 N*N 的矩阵，每一行从左到右有序，每一列从上到下有序，都是递增，写个程序，判断一个数是否在矩阵中。
- HDU 2577 How to Type (DP，经典)
- C#中的==、Equal、ReferenceEqual(转载）
- sqlserver分页;mysql分页;orcale分页 的sql 查询语句
- $resource
- js过滤
- mac下的搭建本地discuz论坛
- js 中ajax请求时设置 http请求头中的x-requestd-with= ajax
- Android Multimedia框架总结（十五）Camera框架之Camera2补充
- java操作XML文件--读取内容
- [51nod1355] 斐波那契的最小公倍数
- Holer下载
- 学习python 检测字符串的方法
- 【UOJ#246】套路（动态规划）
- SQL-存储过程-010
- [No0000162]如何不靠运气致富|来自硅谷著名天使投资人的40条致富经
- <6>Lua元表和冒号 self