js实现深度优先搜索(DFS)和广度优先搜索(BFS)有什么不同,两者相比各适合用于什么情况下

2021-04-06 14:02发布

3条回答
灰机带翅膀
2楼 · 2021-04-07 14:21

一、深度优先搜索(dfs)

① 概念理解:一个人迷路,遇到很多分叉路口,他只有一个人,并且想走出去,所以只能一个个尝试,一条道路走到黑,发现到头了,然后再拐回去走刚才这条路的其他分叉路口,最后发现这条路的所有分叉路口走完了,选择另外一条路继续以上操作,直到所有的路都走过了。实际上就是往深度走,走错了就回来,找没走过的路,直到走到终点。

② 实现方式:堆栈实现,

③ 优点:能找出所有解决方案;相对于bfs内存占用少。

④ 缺点:找到的路径有可能不是最短路径,且在深度较大时效率低。

二、广度优先搜索(bfs)

① 概念理解:一个人迷路,但是他有技能(分身术)它遇到分叉路口,不是选一个走,而是分身多个人都试试,比如有A、B、C三个分叉路口,它A路走一步,紧接着B路也走一步,然后C路也赶紧走一步,步伐整齐统一,直到所有的路走过了。实际上就是往四周搜索,分开搜索。

② 实现方式:队列实现

③ 优点:找到的路径就是最短路径,效率高。

④ 缺点:内存耗费大。


dfs和bfs的最优解情况

① 比较两种算法:广度(bfs)一般无回溯操作,即人栈和出栈的操作,所以运行速度比深度优先搜索法要快些。所以一般情况下,深度(dfs)占内存少但速度较慢,广度(bfs)占内存较多但速度较快,在距离与深度成正比的情况下能较快地求出最优解。

② 如果数据量较大,必须考虑溢出和节省内存空间的问题,使用深度优先搜索法较好,深度优先搜索法有递归以及非递归两种设计方法。一般的,当搜索深度较小、问题递归形式较明显时,用递归方法设计的较好,它可以使得程序结构更简捷易懂。但当搜索深度较大时,当数据量较大时,由于系统堆栈容量的限制,递归易产生溢出,用非递归方法设计比较好

③ 如果数据量较小,且对程序运行的效率要求较高,或者题意是需要找出最短路径,一般使用广度优先搜索法。


嘿呦嘿呦拔萝卜
3楼 · 2021-04-08 11:11

一、深度优先搜索(dfs)

① 概念理解:一个人迷路,遇到很多分叉路口,他只有一个人,并且想走出去,所以只能一个个尝试,一条道路走到黑,发现到头了,然后再拐回去走刚才这条路的其他分叉路口,最后发现这条路的所有分叉路口走完了,选择另外一条路继续以上操作,直到所有的路都走过了。实际上就是往深度走,走错了就回来,找没走过的路,直到走到终点。

② 实现方式:堆栈实现,

③ 优点:能找出所有解决方案;相对于bfs内存占用少。

④ 缺点:找到的路径有可能不是最短路径,且在深度较大时效率低。


py大白
4楼 · 2021-04-09 11:53

一、深度优先搜索(dfs)

① 概念理解:一个人迷路,遇到很多分叉路口,他只有一个人,并且想走出去,所以只能一个个尝试,一条道路走到黑,发现到头了,然后再拐回去走刚才这条路的其他分叉路口,最后发现这条路的所有分叉路口走完了,选择另外一条路继续以上操作,直到所有的路都走过了。实际上就是往深度走,走错了就回来,找没走过的路,直到走到终点。

② 实现方式:堆栈实现,

③ 优点:能找出所有解决方案;相对于bfs内存占用少。

④ 缺点:找到的路径有可能不是最短路径,且在深度较大时效率低。

二、广度优先搜索(bfs)

① 概念理解:一个人迷路,但是他有技能(分身术)它遇到分叉路口,不是选一个走,而是分身多个人都试试,比如有A、B、C三个分叉路口,它A路走一步,紧接着B路也走一步,然后C路也赶紧走一步,步伐整齐统一,直到所有的路走过了。实际上就是往四周搜索,分开搜索。

② 实现方式:队列实现

③ 优点:找到的路径就是最短路径,效率高。

④ 缺点:内存耗费大。


dfs和bfs的最优解情况

① 比较两种算法:广度(bfs)一般无回溯操作,即人栈和出栈的操作,所以运行速度比深度优先搜索法要快些。所以一般情况下,深度(dfs)占内存少但速度较慢,广度(bfs)占内存较多但速度较快,在距离与深度成正比的情况下能较快地求出最优解。

② 如果数据量较大,必须考虑溢出和节省内存空间的问题,使用深度优先搜索法较好,深度优先搜索法有递归以及非递归两种设计方法。一般的,当搜索深度较小、问题递归形式较明显时,用递归方法设计的较好,它可以使得程序结构更简捷易懂。但当搜索深度较大时,当数据量较大时,由于系统堆栈容量的限制,递归易产生溢出,用非递归方法设计比较好

③ 如果数据量较小,且对程序运行的效率要求较高,或者题意是需要找出最短路径,一般使用广度优先搜索法。