以前一直用搜索用的都是深搜，因为听说有很多题能用广搜就能用深搜什么的。今天老老实实的去看广搜了，结果发现我之前想的太天真的，DFS和BFS不仅在性质上不同，而且对于某些题和某些情况，用BFS比DFS要快（不是绝对）。
今天好好说道说道这个BFS（广度优先搜索）
很多问题（如过迷宫问题），每走下一步，都要考虑很多种情况，这个时候，就要每一步每一步的去试探，去找到合适的方案，也是就是传说中的“搜索”。
当然，想试探出结果，可以去将一种方案走到底，遇到不能走或者其他不符合要求的情况再退回来，选择下一个方案继续尝试，这种可以称作所谓的“深度优先搜索”（DFS）;还有一种方式，就是所有方案我先都尝试第一步，检测是否找到结果，如果没有，继续尝试所有方案的第二步。。。。直到找到合适的结果或方案，这种搜索方式成为“宽度优先搜索”。
当然，上面的话是我自己对DFS和BFS的理解和概括，下面是官方的总结（摘自ppt）
优先搜索也称为宽度优先搜索，它是一种先生成的节点先扩展的策略。
广度优先搜索算法如下：（用QUEUE）
把初始节点S0放入Open表中；
如果Open表为空，则问题无解，失败退出；
把Open表的第一个节点取出放入Closed表，并记该节点为n；
考察节点n是否为目标节点。若是，则得到问题的解，成功退出；
若节点n不可扩展，则转第(2)步；
扩展节点n，将其不在Closed表中的子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。
让我们来看看广度优先搜索和深度优先搜索的区别在哪
首先这是我们要搜索的图（图片摘自互联网）：
用深搜：
搜索方式：
路径1 ==> A –> B –> E –> H 路径2 ==> i
路径3 ==> C 路径4 ==> D –> F –> K –> L 路径5 ==> G
用广搜：
搜索方式：
路径1 ==> A 路径2 ==> B –> C –> D 路径3 ==> E –> F –> G
路径4 ==> H –> i –> K 路径5 ==> L
如果要搜的答案在H，那么很显然深搜先搜到
如果答案在D，那么广搜比深搜先搜到
DFS与BFS的效率还是分情况描述的，所以我就不做过多比较。。。
我来说说我总结的广搜过程：
1.建立一个空队列，将根节点Root(搜索的初始第一步)放在队首。
2.Root出队列，同时将Root的所有可能情况（假设s1,s2,s3）压入队列
3.然后判断队首元素(s1)，判断s1是否是可行情况，如果可行，将s1的下一步可行情况压入队列。s1出队列。
4.接下来一直执行2、3两步，直到找到答案或者全部搜索完毕。
如（图画的不好见谅！）
假设需要从1开始，找到5，队列的变换过程如下：
开始1（此时队列中有 1 （下面先后顺序按队首到队尾））
1出队列，将1的可能解2，3加入队列 （此时队列中有 2 ，3）
2出队列，将2的可能解4，5加入队列 （此时队列中有 3，4，5）
3出队列，将3的可能解6，7加入队列 （此时队列中有 4，5，6，7）
4出队列，将4的可能解8，9加入队列 （此时队列中有 5，6，7，8，9）
5出队列，找到答案，结束。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/145430.html