目录
一.基本定义
二.算法步骤
三.算法模板
四.洪水填充法
五.回溯法
六.无权最短路问题
广度优先搜索（BFS）是一种用于图形数据结构的遍历算法，它从给定的起始顶点开始，以广度优先的方式逐层搜索图中的节点，直到找到目标节点或遍历完整个图。BFS算法通常使用队列数据结构来实现，它的时间复杂度为O(V+E)，其中V表示图中顶点数，E表示边数。BFS算法在求解最短路径、连通性、拓扑排序等问题中具有重要应用。
广度优先搜索（Breadth First Search）,简称广搜（BFS）。广搜是逐层扩展状态的搜索策略，常用于解决连通性问题和最短路问题。BFS需要借助队列来实现，不知道什么是队列的小伙伴可以先看一下。
将初始状态入队并标记，队列不为空就循环：取出队首状态，扩展队首状态，如果扩展状态合法，判断其是否是目标状态，如果是目标状态则统计或输出，然后结束循环。值得注意的是，BFS一定要打标记具体作用是防止重复入队造成死循环。
顾名思义，类似于洪水填充，从起点出发，像洪水一般将能连通的地方，全部淹没（染色），这样一来，就很容易统计被淹没区域的信息。洪水填充法也被称为染色法，常用来解决连通快有关的问题。可用DFS实现也可用BFS实现不同的是，DFS需要耗费更多的栈空间
洪水填充法（Flood Fill）是一种图像处理算法，用于将一个连通区域内所有像素点的颜色值替换为指定颜色。该算法通常用于图像编辑软件中的画图工具，如涂鸦、填充等功能。
Flood Fill算法是基于递归或者队列实现的，其基本思想是从指定的起点开始，向周围扩展，如果周围的像素点与起点颜色相同，则将其替换为目标颜色，并继续向周围扩展，直到找到不同颜色的像素点为止。
你可能会问洪水填充法，能用BFS实现那，在基于DFS的"万能算法"，能用BFS实现吗，当然可以。不过用BFS实现空间开销非常大，需要把整个局面给存下来，且代码实现细节繁琐，所有一般不使用。
看到这里你可能会觉得BFS对比DFS好像没有任何优势，但事实上由于BFS是层次遍历所以非常擅长求解最短路问题。采用DFS求最短路，需要尝试能到达终点的所有路径而确定最短路径，而BFS第一次到达终点时就是最短路径，但层次深度和路径长度必须成正比，这一类问题，被称作无权最短路问题，可以通过BFS高效求解
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/bcyy/20690.html