宽搜和深搜的区别

Question

个位大侠。。。小弟愚昧，不知道宽搜和深搜有什么区别，什么时候用宽搜好什么时候用深搜好？请大侠们指点。。。

Answer 1

首先你要知道什么叫搜索树,也就是根据本次搜索扩展出下个搜索节点的树形图. 那么广度(宽度)优先搜索就是一层一层的遍历搜索树, 而深度优先是先一搜到底再回溯. 可以理解为:广搜是按步列举出每一次所有的可能情况. 而深搜是"先按一种可能搜下去,如果不行了(即不符合条件)就返回上一次的地方再试探下一种可能性. 一般来说,广搜常用于找单一的最短路线,或者是规模小的路径搜索,它的特点是"搜到就是最优解", 而深搜用于找多个解或者是"步数已知(比如3步就必须达到条件)"的问题,它的空间效率高,但是找到的不一定是最优解,必须记录并完成整个搜索,故一般情况下,深搜需要非常高效的剪枝(优化). 具体的建议看看 http://jsjkx.bzu.edu.cn/jpkc/ds/resource/flash/dfs.swf 和 http://jsjkx.bzu.edu.cn/jpkc/ds/resource/flash/bfs.swf 的动画,有助于帮助理解

Answer 2

深度搜索是数据结构中 树形结构的一种遍历方法 所谓遍历 就是一个一个查找 搜索就是遍历所有结点并且检查关键字是否匹配 树的深度搜索和广度搜索区别就是 深度搜索是按照深度优先原则 先笔直往下找子结点 找到那个结点后 又找这个结点的子结点 广度是按照以层为优先进行搜索 树都是一层一层的 找到一个结点后 又找这个结点的兄弟结点 （一般两个都是从左往右 你是天才的话 也许可以从右往左）本回答被网友采纳

Answer 3

宽搜是用队列来实现，深搜是用栈。宽搜一般用来寻找最短路径，深搜一般用来寻找可行路径。

Answer 4

　　宽搜：
　　宽搜是宽度优先搜索的简称，宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
　　深搜：
　　深搜是深度优先搜索的简称，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的节点，如果它还有以此为起点而未搜索的边，就沿此边继续搜索下去。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v有那条边的始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被发现为止。
　　树的深搜和宽搜的区别：
　　深度搜索是按照深度优先原则，先笔直往下找子结点 找到那个结点后，又找这个结点的子结点，广度是按照以层为优先进行搜索，树都是一层一层的，找到一个结点后，又找这个结点的兄弟结点。宽搜是用队列来实现，深搜是用栈。