广度优先搜索(BFS)与深度优先搜索(DFS)的对比及优缺点

冷不防 2023-07-07 03:55 34阅读 0赞

深搜，顾名思义，是深入其中、直取结果的一种搜索方法

如果深搜是一个人，那么他的性格一定倔得像头牛！他从一点出发去旅游，只朝着一个方向走，除非路断了，他绝不改变方向！除非四个方向全都不通或遇到终点，他绝不后退一步！因此，他的姐姐广搜总是嘲笑他，说他是个一根筋、不撞南墙不回头的家伙。

深搜很讨厌他姐姐的嘲笑，但又不想跟自己的亲姐姐闹矛盾，于是他决定给姐姐讲述自己旅途中的经历，来改善姐姐对他的看法。他成功了，而且只讲了一次。从那以后他姐姐不仅再没有嘲笑过他，而且连看他的眼神都充满了赞赏。他以为是自己路上的各种英勇征服了姐姐，但他不知道，其实另有原因……

深搜是这样跟姐姐讲的：关于旅行呢，我并不把目的地的风光放在第一位，而是更注重于沿路的风景，所以我不会去追求最短路，而是把所有能通向终点的路都走一遍。可是我并不知道往哪走能到达目的地，于是我只能每到一个地方，就向当地的人请教各个方向的道路情况。

为了避免重复向别人问同一个方向，我就给自己规定：先问北，如果有路，那就往北走，到达下一个地方的时候就在执行此规定，如果往北不通，我就再问西，其次是南、东，要是这四个方向都不通或者抵达了终点，那我回到上一个地方，继续探索其他没去过的方向。我还要求自己要记住那些帮过他的人，但是那些给我帮倒忙的、让我白费力气的人，要忘记他们。有了这些规定之后，我就可以大胆的往前走了，既不用担心到不了不目的地，也不用担心重复走以前的路。哈哈哈……

### 深搜优缺点 ###

优点

*  能找出所有解决方案
 *  优先搜索一棵子树，然后是另一棵，所以和广搜对比，有着内存需要相对较少的优点

缺点

*  要多次遍历，搜索所有可能路径，标识做了之后还要取消。
 *  在深度很大的情况下效率不高

使用场景：性格测试的游戏

> 参考文章：[https://segmentfault.com/a/1190000010563179][https_segmentfault.com_a_1190000010563179]

--------------------

广搜，顾名思义，是多管齐下、广撒网的一种搜索方法

如果广搜是一个人，那么她一定很贪心，而且喜新厌旧！她从一点出发去旅游，先把与起点相邻的地方全部游览一遍，然后再把与她刚游览过的景点相邻的景点全都游览一边……一直这样，直至所有的景点都游览一遍。

广搜属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2…Vit，并均标记为已访问过，然后再按照Vi1、Vi2…Vit 的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。

### 广搜优缺点 ###

优点

*  对于解决最短或最少问题特别有效，而且寻找深度小
 *  每个结点只访问一遍，结点总是以最短路径被访问，所以第二次路径确定不会比第一次短

缺点

*  内存耗费量大（需要开大量的数组单元用来存储状态）

使用场景：计算网络数据链路层的最短跳数，走迷宫的最短路径

[https_segmentfault.com_a_1190000010563179]: https://segmentfault.com/a/1190000010563179