广度优先搜索详解--BFS--蒟蒻的学习之路

1.什么是广度优先搜索?

广度优先搜索（Breadth-First Search，简称BFS）是一种遍历或搜索树和图的算法，也称为宽度优先搜索，BFS算法从图的某个节点开始，依次对其所有相邻节点进行探索和遍历，然后再对这些相邻节点的相邻节点进行探索，直到遍历完所有的节点。

2.c++与c语言的实现的不同

c++ BFS算法使用队列来辅助实现,c语言往往通过数组来辅助实现(后面会有不同的样例来解释不同的语言的实现形式)c语言看起来可能有点啊难理解，需要通过模拟队列!

3.BFS的使用场景

一般来说广度优先搜索适用于解决两点之间的最短路径问题

广度优先搜索是从起点出发，以起点为中心，一圈一圈搜索的，一旦找到终点，记录之前走过的节点，这样就是一条最短路径

BFS常用于寻找最短路径,数据小的最短路径可以用DFS,大点的用DFS会超时,之前写过一道,这样子的题型

DFS/BFS算法在蓝桥杯竞赛中很常见。几乎每一年都会考到DFS/BFS算法!

4.BFS的使用步骤

将起始节点放入队列中,然后将起点标记为已经访问过，然后依次取出队列中的节点，访问其相邻节点，并将其加入队列。这样可以保证从起始节点出发，依次按照距离顺序遍历节点。因为它按照从起点到每个节点的距离来探索节点。

BFS算法通常使用队列来实现，BFS算法的具体步骤如下：

创建一个队列，将起始节点加入队列；创建一个集合，用于存储已经访问过的节点；从队列中取出一个节点，并将其标记为已访问；访问该节点的所有相邻节点，如果相邻节点未被访问，则将其加入队列；重复步骤3和步骤4，直到队列为空。

5.算法模板：

首先我们需要一个队列来辅助BFS实现，还需要一个初始化的输入数组，还有一个标记数组。先找到BFS的起点跟终点，确定好之后，先把起点vis==1，把起点入队，然后进入BFS函数，进入BFS函数一般先是一个大while循环，来管理队列的入队、出队。由于点都是二维的，我们一般都是用pair或者结构体来表示点，新建一个点来存储队头的信息，存完就可以让队头出队了。然后判断是否到达了目标结点，一个if判断，下面就是跟dfs一样，一个for循环遍历周围所有的点，不合法的直接continue掉，合法的标记完vis后入队，有的题目会有回溯，像在部分最短路搜索。

queue<node> q; void bfs(){ while(!q.empty()){ node tmp=q.top();//node为(x,y)结构体 q.pop();//出队 if(到达目标终点){ 更新 return; } //有的会有剪枝 for(int i=0;i<m;i++){//m个方向 int dx=tmp.x+bx[i]; int dy=tmp.y+by[i]; if(下标越界){ continue; } if(已经被标记过了){ continue; } //否则就是合法的 vis[dx][dy]=1;//先标记 q.push(node{dx,dy});//再新点入队 } } } 6.例题讲解 

P1135 奇怪的电梯 - 洛谷

 这里有一个需要注意的地方for输入的时候要记得从1开始因为上下娄底要用到这个准确的位置下标

#include<bits/stdc++.h> using namespace std; #define N 400 int a[N];//接收上下楼梯的值 int visu[N];//判断当前楼层是否被访问 int n, Start, End; struct pos {//表示当前状态     int level;//目前的当层楼层     int step;//到当前楼层的步数 }; void bfs(); int main() {     while (cin >> n) {         if (n == 0)break;         cin >> Start >> End;         for (int i = 1; i <= n; i++) {             visu[i] = 0;             cin >> a[i];         }         bfs();     }     return 0; } void bfs() {     pos cur, next;//定义两个变量     cur.level = Start;//接受初始值的楼梯层数状态     cur.step = 0;     queue<pos>qu;//队列qu变量     qu.push(cur);//输入cur     visu[Start] = 1;//表示当前楼层已经被访问     while (!qu.empty()) {//如果队列不为空         cur = qu.front();//cur接受首元素位置         qu.pop();//弹出首元素位置         if (cur.level == End) {//如果起点等于终点//打印当前步数(开始错在此处,因为写成start1==end,start1是没有变化的,所以不行)             printf("%d", cur.step);             return;         }         next.level = cur.level + a[cur.level];//向上走         next.step = cur.step + 1;//步数加一         if (next.level <= n) {             if (visu[next.level] == 0) {                 visu[next.level] = 1;                 qu.push(next);             }         }         next.level = cur.level - a[cur.level];         next.step = cur.step + 1;         if (next.level >= 1) {             if (visu[next.level] == 0) {                 visu[next.level] = 1;                 qu.push(next);             }         }     }     cout << "-1" << endl;//最后实在没有找到返回-1     return; }

已补上c语言表现形式

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int n, start, next; int a[1000], vis[1000]; struct pos { int h, step; }q[1000]; void bfs() { int front = 1, rear = 1; q[rear].h = start; q[rear].step = 0; rear++; vis[start] = 1; while (front < rear) { struct pos cur, net; cur = q[front]; front++; if (cur.h == next) { printf("%d", cur.step); return; } net.h = cur.h + a[cur.h]; net.step = cur.step + 1; if (net.h <= n && net.h >= 1 && vis[net.h] == 0) { vis[net.h] = 1; q[rear] = net; rear++; } net.h = cur.h - a[cur.h]; net.step = cur.step + 1; if (net.h <= n && net.h >= 1 && vis[net.h] == 0) { vis[net.h] = 1; q[rear] = net; rear++; } } printf("-1"); return; } int main() { scanf("%d%d%d", &n, &start, &next); for (int i = 1; i <= n; i++)scanf("%d", &a[i]); bfs(); return 0; }