广度优先搜索（BFS）详解

目录

一.基本定义

二.算法步骤

三.算法模板

四.洪水填充法

五.回溯法

六.无权最短路问题

---

一.基本定义

广度优先搜索（BFS）是一种用于图形数据结构的遍历算法，它从给定的起始顶点开始，以广度优先的方式逐层搜索图中的节点，直到找到目标节点或遍历完整个图。BFS算法通常使用队列数据结构来实现，它的时间复杂度为O(V+E)，其中V表示图中顶点数，E表示边数。BFS算法在求解最短路径、连通性、拓扑排序等问题中具有重要应用。

      广度优先搜索（Breadth First Search）,简称广搜（BFS）。广搜是逐层扩展状态的搜索策略，常用于解决连通性问题和最短路问题。BFS需要借助队列来实现，不知道什么是队列的小伙伴可以先看一下这篇博客。

二.算法步骤

       将初始状态入队并标记，队列不为空就循环：取出队首状态，扩展队首状态，如果扩展状态合法，判断其是否是目标状态，如果是目标状态则统计或输出，然后结束循环。值得注意的是，BFS一定要打标记具体作用是防止重复入队造成死循环。

三.算法模板

queue<A> q;
q.push(初始状态);
将初始状态标记；
while(!q.empty()){
    A u=q.front();
    q.pop();
    for(枚举u所有可能的扩张状态v){
        if(v是合法的状态){
            标记v;
            q.push(v);
            if(是目标状态){
                统计或输出;
                return 0;
            }
        }
    }
}
输出无解

四.洪水填充法

      顾名思义，类似于洪水填充，从起点出发，像洪水一般将能连通的地方，全部淹没（染色），这样一来，就很容易统计被淹没区域的信息。洪水填充法也被称为染色法，常用来解决连通快有关的问题。可用DFS实现也可用BFS实现不同的是，DFS需要耗费更多的栈空间

        洪水填充法（Flood Fill）是一种图像处理算法，用于将一个连通区域内所有像素点的颜色值替换为指定颜色。该算法通常用于图像编辑软件中的画图工具，如涂鸦、填充等功能。

        Flood Fill算法是基于递归或者队列实现的，其基本思想是从指定的起点开始，向周围扩展，如果周围的像素点与起点颜色相同，则将其替换为目标颜色，并继续向周围扩展，直到找到不同颜色的像素点为止。

五.回溯法

        你可能会问洪水填充法，能用BFS实现那，在基于DFS的"万能算法"，能用BFS实现吗，当然可以。不过用BFS实现空间开销非常大，需要把整个局面给存下来，且代码实现细节繁琐，所有一般不使用。

六.无权最短路问题

        看到这里你可能会觉得BFS对比DFS好像没有任何优势，但事实上由于BFS是层次遍历所以非常擅长求解最短路问题。采用DFS求最短路，需要尝试能到达终点的所有路径而确定最短路径，而BFS第一次到达终点时就是最短路径，但层次深度和路径长度必须成正比，这一类问题，被称作无权最短路问题，可以通过BFS高效求解