【总结】BFS 模板总结及例题详解

小鱼儿 2023-07-03 03:21 14阅读 0赞

###  ###

*  广度优先搜索
 *  BFS 模板套路
 *  BFS 经典题目

> 以下内容收集了全网以及整合了自己写的部分。

# 广度优先搜索 #

*  广度优先搜索算法（也称宽度优先搜索，英语：Breadth-First Sear，缩写BFS），是连通图的一种遍历策略。其思想是从一个顶点开始，辐射状地优先遍历其周围较广的区域。通俗易懂地讲，请看下图。

整个过程的实例图如图所示：

1、初始全部都是白色（未访问）  
![在这里插入图片描述][20200203140149580.png]  
2、即将搜索起点V0（灰色）  
![在这里插入图片描述][20200203140258856.png]  
3、已搜索V0，即将搜索V1、V2、V3  
![在这里插入图片描述][20200203140311317.png]  
4、终点V6被染灰色，终止  
![在这里插入图片描述][20200203140347962.png]  
5、找到最短路径  
![在这里插入图片描述][20200203140406943.png]

整个过程的流程图如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]

*  **DFS和BFS的区别：** 深搜和广搜在实现上分别用的是栈（栈和函数递归本质是一样）和队列。一般来说，广搜常用于找单一的最短路线，或者是规模小的路径搜索，它的特点是"搜到就是最优解"， 而深搜用于找多个解或者是"步数已知（好比3步就必需达到前提）"的标题，它的空间效率高，然则找到的不必定是最优解，必需记实并完成全数搜索，故一般情况下，深搜需要很是高效的剪枝（优化）.

# BFS 模板套路 #

**简单版**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70 1]  
**详细版**

//模板1
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int maxn=100;
    bool vst[maxn][maxn]; // 访问标记
    int dir[4][2]={ 0,1,0,-1,1,0,-1,0}; // 方向向量
    
    struct State // BFS 队列中的状态数据结构
    { 
    	int x,y; // 坐标位置
    	int Step_Counter; // 搜索步数统计器
    };
    
    State a[maxn];
    
    bool CheckState(State s) // 约束条件检验
    { 
    	if(!vst[s.x][s.y] && ...) // 满足条件
    		return 1;
    	else // 约束条件冲突
    		return 0;
    }
    
    void bfs(State st)
    { 
    	queue <State> q; // BFS 队列
    	State now,next; // 定义2 个状态，当前和下一个
    	st.Step_Counter=0; // 计数器清零
    	q.push(st); // 入队
    	vst[st.x][st.y]=1; // 访问标记
    	while(!q.empty()){ 
    		now=q.front(); // 取队首元素进行扩展
    		if(now==G){  // 出现目标态，此时为Step_Counter 的最小值，可以退出即可
    			...... // 做相关处理
    			return;
    		}
    		for(int i=0;i<4;i++){ 
    			next.x=now.x+dir[i][0]; // 按照规则生成下一个状态
    			next.y=now.y+dir[i][1];
    			next.Step_Counter=now.Step_Counter+1; // 计数器加1
    			if(CheckState(next)){  // 如果状态满足约束条件则入队
    				q.push(next);
    				vst[next.x][next.y]=1; //访问标记
    			}
    		}
    		q.pop(); // 队首元素出队 
    	}
    	return;
    }
    
    int main()
    { 
    	......
    	 return 0;
    }

# BFS 经典题目 #

*  [【POJ】3984 迷宫问题 （入门）][POJ_3984 _]

> 题解：

[20200203140149580.png]: https://img-blog.csdnimg.cn/20200203140149580.png
[20200203140258856.png]: https://img-blog.csdnimg.cn/20200203140258856.png
[20200203140311317.png]: https://img-blog.csdnimg.cn/20200203140311317.png
[20200203140347962.png]: https://img-blog.csdnimg.cn/20200203140347962.png
[20200203140406943.png]: https://img-blog.csdnimg.cn/20200203140406943.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200203141025784.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200129230222575.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA==,size_16,color_FFFFFF,t_70
[POJ_3984 _]: http://poj.org/problem?id=3984