一、深度优先搜索(dfs)
① 概念理解:一个人迷路,遇到很多分叉路口,他只有一个人,并且想走出去,所以只能一个个尝试,一条道路走到黑,发现到头了,然后再拐回去走刚才这条路的其他分叉路口,最后发现这条路的所有分叉路口走完了,选择另外一条路继续以上操作,直到所有的路都走过了。实际上就是往深度走,走错了就回来,找没走过的路,直到走到终点。
② 实现方式:堆栈实现,
③ 优点:能找出所有解决方案;相对于bfs内存占用少。
④ 缺点:找到的路径有可能不是最短路径,且在深度较大时效率低。
二、广度优先搜索(bfs)
① 概念理解:一个人迷路,但是他有技能(分身术)它遇到分叉路口,不是选一个走,而是分身多个人都试试,比如有A、B、C三个分叉路口,它A路走一步,紧接着B路也走一步,然后C路也赶紧走一步,步伐整齐统一,直到所有的路走过了。实际上就是往四周搜索,分开搜索。
② 实现方式:队列实现
③ 优点:找到的路径就是最短路径,效率高。
④ 缺点:内存耗费大。
dfs和bfs的最优解情况
① 比较两种算法:广度(bfs)一般无回溯操作,即人栈和出栈的操作,所以运行速度比深度优先搜索法要快些。所以一般情况下,深度(dfs)占内存少但速度较慢,广度(bfs)占内存较多但速度较快,在距离与深度成正比的情况下能较快地求出最优解。
② 如果数据量较大,必须考虑溢出和节省内存空间的问题,使用深度优先搜索法较好,深度优先搜索法有递归以及非递归两种设计方法。一般的,当搜索深度较小、问题递归形式较明显时,用递归方法设计的较好,它可以使得程序结构更简捷易懂。但当搜索深度较大时,当数据量较大时,由于系统堆栈容量的限制,递归易产生溢出,用非递归方法设计比较好
③ 如果数据量较小,且对程序运行的效率要求较高,或者题意是需要找出最短路径,一般使用广度优先搜索法。