广度优先搜索也称为宽度优先搜索，简称广搜或者 BFS，是遍历图存储结构的一种算法，既适用于无向图（网），也适用于有向图（网）。
广度优先搜索以队列（deque）作为核心，其搜索核心是从始结点开始，寻找一步到达的合法可行点（可能存在其他条件限制），并加入队列，然后弹出始结点，由依次对队列中的结点执行寻找操作，直至队列为空。
我们首先创造一个队列，将初始结点V1加入，并且标记为已访问：
寻找从V1邻接点（可一步到达的点），加入队列中，标记结点已访问。
将头结点（V1）弹出队列。 
重复上一步，寻找V2的未被访问的邻接点，加入，标记结点已访问。
弹出头结点V2：
寻找V3的未被访问的邻接点，并加入队列中，标记结点已访问：
弹出头结点V3，
将V4作为头结点去寻找未被访问过的邻接点，并加入队列中，标记结点已访问：
接下来，寻找V5的邻接点，发现是V8，但是V8已被访问过，故不做处理，弹出V5：
至此，图被完全遍历。
在暴力算法中，BFS被广泛用于求无权图的最短路径问题，因为BFS的操作其实就是类似于向平静的湖面投石子引起的一圈圈涟漪，最先碰到涟漪的鱼一定就是离石头最近的点。
以下是自我总结的模版
void bfs() { queue<int>q; q.push(root); st[root]=true; while(q.size()) { int t=q.front(); q.pop(); cout<<t<<" "; for(auto i:z[t]) { if(!st[i]) { st[i]=true; q.push(i); } } } }
例题
题解
#include<iostream> #include<queue> using namespace std; int n, m; int x, y; char a[50][50];//存迷宫的初始状态 int dis[50][50];//记录走过的所有距离 bool st[50][50];//判断这个点是否走过 int dx[4] = { 0,0,1,-1 };// int dy[4] = { 1,-1,0,0 };//两者结合判断上下左右的方向 void bfs() { queue<pair<int, int>>q; //queue嵌套pair 可以记录当前的坐标 memset(dis, -1, sizeof dis); //将所有值都变成-1,如果输出-1则代表无法到达终点 dis[1][1] = 1; //初始点为第1步 st[1][1] = true; //特判标记 q.push({ 1,1 }); //将1,1坐标push进pair 代表从1,1开始了 while (!q.empty()) //q还有值 { auto f = q.front(); q.pop(); //将该值弹出去 寻找下一个方向 int x = f.first; //x 为pair的第一个值 int y = f.second;//y 为pair的第二个值 for (int i = 0; i < 4; i++) { int tx = x + dx[i]; int ty = y + dy[i];//四个方向都遍历一遍 if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] == '.' && st[tx][ty] == false)//tx,ty都在界,下一个方向是'.'且这个地方没走过 { st[tx][ty] = true; //标记该地点 dis[tx][ty] = dis[x][y] + 1; //距离+1 q.push({ tx,ty });//pair记录该点的坐标 } } } cout << dis[n][m]; //输出步数 } signed main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } bfs(); return 0; }
