广度优先搜索，即广搜，也称宽度优先搜索 ( Breadth First Search )，是一种搜索算法，广搜使用队列来实现 ( 所以意思就是你得知道什么是队列 )
所谓队列，就是队列，是一种非常常用的数据结构，同时，它也是一种线性表 ( 好吧其实可以理解为数组 )，里面装了广搜每一步的信息
我们仍然以上一次讲深搜时使用的迷宫 ( 绝对不是懒得画图 )
这样子，z 队列就实现了它的价值，用于记录每一步，它可以为下一步提供帮助，也可以保存答案
广搜的 while 循环中 h 是程序走到的地方，即在 z 数组中的下标，t 是已有的路径中的坐标，也可以说 h 直到 t 都是可以走的下一步，就等待 h 进行处理，这样循环下去，当 h = t 时，就说明下一步没有路了，也就结束了循环
mov 即移动数组，视情况而改变，有时候可能不一样，在 for 中循环枚举下一步的位置，通过对 z 数组 h 位置的 x 和 y 坐标的加减可以推断出下一步的位置
推断出下一步后 if 判断 nx ny 这个位置是否能够走，其中的内容也是视情况而定的，将所有必要的条件都放入进去，例如这个点 ( nx , ny ) 不能为 1 ( Map[nx][ny]!=1 )，这个点不能被走过 ( !data[nx][ny] )，这个点不能越界 ( nx>=0&&ny>=0&&nx<10&&ny<10 ) 等等
如果这些条件都满足了，就可以进行下一步，将这个新的点加入至 z 数组中，等待 h 来处理，两个赋值操作都是将新的点的坐标记录下来，t++ 会将可用的位置增加 1，最后别忘了将走过了的标记也赋值，最后一个 if 就是用于判断是否成功到达了这个点
广搜的遍历就像是一棵树，就像这张图
如果用广搜搜索，就会以这样的方式遍历
从一开始，拓展 2，3，4，然后开始拓展 2 得到 5，6，拓展 3 得到 7，拓展 4 得到 8
然后又开始拓展由 2 得到的 5 得到 9，拓展 6 得到 10，拓展 7 得到 11，拓展 8 得到 12 和 13，依次类推，最后拓展 12 时就会发现最终答案 16
总的来说，广搜是比较好理解的，没有深搜那样的递归回溯，并且利用队列来执行
深搜的处理方式就是一路搜到底，没路了才一步步回溯；而广搜将所有可用的点放入数列中，等到之后再利用这些点继续拓展
广搜与深搜都是按照顺序遍历每一个点，只是方向不一样
另外广搜和深搜不一定只是用在图中的，它们同样可以用在其它地方
好的如果你觉得本篇文章对你有所帮助的话请不要忘记支持！
题解还在肝
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/151345.html