常用于

在一幅「图」中找到从起点 start 到终点 target 的最近距离
比如说两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次

比如说连连看游戏，两个方块消除的条件不仅仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个坐标，游戏是如何判断它俩的最短连线有几个拐点的？

code

```cpp // 计算从起点 start 到终点 target 的最近距离 int BFS(Node start, Node target) { Queue q; // 核心数据结构 Set visited; // 避免走回头路

q.offer(start); // 将起点加入队列 visited.add(start); int step = 0; // 记录扩散的步数

while (q not empty) {

  int sz = q.size();
  /* 将当前队列中的所有节点向四周扩散 */
  for (int i = 0; i < sz; i++) {
      Node cur = q.poll();
      /* 划重点：这里判断是否到达终点 */
      if (cur is target)
          return step;
      /* 将 cur 的相邻节点加入队列 */
      for (Node x : cur.adj())
          if (x not in visited) {
              q.offer(x);
              visited.add(x);
          }
  }
  /* 划重点：更新步数在这里 */
  step++;

} }

<a name="el3Oz"></a>
# 原理
 BFS 的逻辑，depth 每增加一次，队列中的所有节点都向前迈一步，这保证了第一次到达终点的时候，走的步数是最少的<br />DFS 实际上是靠递归的堆栈记录走过的路径，要找到最短路径，肯定得把二叉树中所有树杈都探索完才能对比出最短的路径有多长——所以时间复杂度会很高<br />而 BFS 借助队列做到一次一步「齐头并进」，是可以在不遍历完整棵树的条件下找到最短距离的。
> 形象点说，DFS 是线，BFS 是面；DFS 是单打独斗，BFS 是集体行动。这个应该比较容易理解吧。
<a name="L6mM7"></a>
# 来点题目
<a name="i6J2U"></a>
## [leetcode [111. 二叉树的最小深度]C++|BFS](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/111-er-cha-shu-de-zui-xiao-shen-du-cbfs-6mtbr/)
<a name="Owi6F"></a>
## L2-031 深入虎穴 (25 分)
[https://pintia.cn/problem-sets/994805046380707840/problems/1111914599412858888](https://pintia.cn/problem-sets/994805046380707840/problems/1111914599412858888)
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i =n;i<m;++i)
const int N = 100010;
bool vis[N];
int n, k, d;
vector<int> edge[N];//存边
queue<int> q;//BFS要用
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    FOR(i,1,n+1){
        cin>>k;
        while(k--){
            cin>>d;
            //无向边，所以两边都要加上
            edge[i].push_back(d);
            edge[d].push_back(i);
        }
    }
    q.push(1);//从第一个编号开始
    vis[1]=1;
    int one;
    while(!q.empty()){
        one = q.front();
        q.pop();
        for(auto v:edge[one]){//遍历该点能到的点
            if(vis[v])continue;//访问过就跳过
            vis[v] = 1;//记得记录
            q.push(v);
        }
    }
    cout<<one;//记录的队列中的最后一个 就是离入口最远的点。
    return 0;
}

L3-004 肿瘤诊断 (30 分) | 三维地图

三维的广度优先搜索：XYZ三个数组判断方向，
对每一个点广度优先累计肿瘤块的大小，如果大于等于t就把结果累加。
用visit数组标记当前的点有没有被访问过，被访问过的结点是不会再访问的。
judge判断是否超过了边界，或者是否当前结点为0不是肿瘤

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i =n;i<m;++i)
struct node{
    int x, y, z;
};
int m, n, l, t;
//方向选择
int X[6] = {1, 0, 0, -1, 0, 0};
int Y[6] = {0, 1, 0, 0, -1, 0};
int Z[6] = {0, 0, 1, 0, 0, -1};
int arr[1300][130][80];//地图
bool vis[1300][130][80];//标记
//判断:过滤越界|已经标记过|是0 情况
bool judge(int x, int y, int z){
    if(x < 0 || x >= m || y < 0 || y >= n ||
       z < 0 || z >= l) return false;
    if(arr[x][y][z] == 0 || vis[x][y][z] == 1) return false;
    return true;
}
//广搜
int bfs(int x, int y, int z){
    int cnt = 0;//这个连通块的大小
    node tmp={x, y, z};
    queue<node> q;
    q.push(tmp);
    vis[x][y][z] = 1;//标记
    while(!q.empty()){
        node top = q.front();
        q.pop();
        cnt++;//
        for(int i = 0; i<6;i++){
            //六个方向查找
            int tx = top.x + X[i],
                ty = top.y + Y[i],
                tz = top.z + Z[i];
            if(judge(tx, ty, tz)){
                vis[tx][ty][tz] = 1;
                node tmp2={tx, ty, tz};
                q.push(tmp2);
            }
        }
    }
    if(cnt >= t)return cnt; //够大
    else return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>m>>n>>l>>t;
    FOR(i,0,l)
        FOR(j,0,m)
            FOR(k,0,n)
                cin>>arr[j][k][i];
    int ans = 0;
    FOR(i,0,l)
        FOR(j,0,m)
            FOR(k,0,n)
                if(arr[j][k][i] == 1 && !vis[j][k][i])
                    ans += bfs(j,k,i);
    cout<<ans;
    return 0;
}

Web 开发学习笔记

BFS ——迷宫最短路

常用于

code

L3-004 肿瘤诊断 (30 分) | 三维地图