目录

DFS和BFS

DFS(Deep First Search)深度优先搜索。

深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义,深度优先,则是以深度为准则,先一条路走到底,直到达到目标。这里称之为递归下去。 否则既没有达到目标又无路可走了,那么则退回到上一步的状态,走其他路。这便是回溯上来。 DFS的案例可以在我的这几篇博客里找到:

BFS(Breath First Search)广度优先搜索。

广度优先搜索较之深度优先搜索之不同在于,深度优先搜索旨在不管有多少条岔路,先一条路走到底,不成功就返回上一个路口然后就选择下一条岔路,而广度优先搜索旨在面临一个路口时,把所有的岔路口都记下来,然后选择其中一个进入,然后将它的分路情况记录下来,然后再返回来进入另外一个岔路,并重复这样的操作 BFS的经典案例求迷宫最短路径参看我的这篇博客 迷宫最短路径

总结

BFS 常用于找单一的最短路线,它的特点是 “搜到就是最优解”,而DFS用于找所有解的问题,它的空间效率高,而且找到的不一定是最优解,必须记录并完成整个搜索,故一般情况下,深搜需要非常高效的剪枝(剪枝的概念请百度)。