深度优先搜索会优先 “把一条路走到黑” ，而广度优先搜索（BFS）则是每一步都检查所有方案。在求解最少步数到达目标状态的问题上，bfs 一旦找到一条可行路径，那么它一定也是最短路径。

树的层次遍历就是典型的 bfs，这种算法使用到队列结构。你可以使用 STL 的 queue 。注意在要求记录路径等情况复杂时，可能使用数组模拟队列会是更好的选择，这样在元素出队后不会丢失路径信息。

例题 1：[USACO 2007 Ope S]Catch That Cow

抓住那头牛

时限： 2000MS 内存限制： 65536K

描述

农夫约翰已被告知一头逃亡母牛的位置，并希望立即抓住它。他从数轴上的点N (0 ≤ N ≤ 100,000) 开始，而奶牛在同一数轴上的点K (0 ≤ K ≤ 100,000) 处。Farmer John 有两种交通方式：步行和传送。

  • 行走：FJ 可以在一分钟内从X点移动到X - 1 或X + 1点
  • 传送：FJ 可以在一分钟内从X点移动到 2 × X点。

如果母牛不知道它的追逐，根本不动，农夫约翰需要多长时间才能把它取回？

输入

第 1 行：两个空格分隔的整数：N 和 K

输出

第 1 行：Farmer John 抓住逃亡母牛所需的最少时间（以分钟为单位）。

样例输入 5 17

样例输出 4

提示

Farmer John 到达逃亡母牛的最快方式是沿着以下路径移动：5-10-9-18-17，需要 4 分钟。

此题使用 dfs 的情况，程序会找到经过 100,000 个点的所有可行路径，在完成搜索前并不能确定有没有更好的答案，这并不是一个明智的做法。我们通过简单思考，可以发现此题的答案在大部分情况下是通过合理使用传送的一条较短路径。使用 bfs ，每次找到当前步数下所有的走法。当程序找到一条合法路径，所有步数更少的方案已经经过搜索，被验证不存在合法方案，因此程序找到的第一条路径就是最短路径。

参考代码 1
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pii;        // node, steps count
  4. const int N = 100000;
  5. bool vis[N + 4];
  6. queue<pii> q;
  7. int n, k;
  8. // 判断访问该点是否合法
  9. inline bool ok(int x) {
  10.     return x >= 0 && x <= N && !vis[x];
  11. }
  12. int bfs() {
  13.     q.push(pii(n, 0));
  14.     while (1) {
  15.         // 取出队首元素
  16.         int x = q.front().first;
  17.         int cnt = q.front().second;
  18.         q.pop();
  19.         if (x == k) {
  20.             return cnt;    // 找到的第一个路线一定是最优解
  21.         }
  22.         vis[x] = true;
  23.         // 把合法的下一步加入队列
  24.         if (ok(x - 1))
  25.             q.push(pii(x - 1, cnt + 1));
  26.         if (ok(x + 1))
  27.             q.push(pii(x + 1, cnt + 1));
  28.         if (ok(x * 2))
  29.             q.push(pii(x * 2, cnt + 1));
  30.     }
  31. }
  32. int main() {
  33.     cin >> n >> k;
  34.     cout << bfs() << endl;
  35.     return 0;
  36. }

代码中 pair<int, int> 的使用避免了声明一个结构体，是一种简便写法。

类似 DFS 的思路，我们同样可以把对线段上点之间移动的 BFS 抽象地看成决策树上每一步所做决策的 bfs。

例题 2：力扣 752. 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

参考代码 2
  1. class Solution {
  2. public:
  3.     /** 
  4.      * @positive 表示旋转方向。为真时，令数字向增加方向旋转
  5.      * @return 返回当前数字 @c 拨动一位后的显示数字
  6.      */
  7.     inline char trans(char c, bool positive) {
  8.         if (positive) {
  9.             return c == '9' ? '0' : c + 1;
  10.         } else {
  11.             return c == '0' ? '9' : c - 1;
  12.         }
  13.     }
  14.     int openLock(vector<string>& deadends, string target) {
  15.         using P = pair<string, int>;
  16.         unordered_set<string> dead;
  17.         unordered_set<string> vis;
  18.         for (const string& d : deadends) {
  19.             dead.insert(d);
  20.         }
  21.         string cur = "0000";
  22.         queue<P> q;
  23.         q.push({cur, 0});        // C++11
  24.         while (!q.empty()) {
  25.             P p = q.front();
  26.             q.pop();
  27.             if (p.first == target) {    // 终止：找到答案
  28.                 return p.second;
  29.             }
  30.             if (dead.count(p.first) || vis.count(p.first)) {
  31.                 continue;
  32.             }
  33.             vis.insert(p.first);
  34.             for (int i=0; i<4; ++i) {    // 遍历四个数字位
  35.                 // 正转
  36.                 string t = p.first;
  37.                 t[i] = trans(t[i], true);
  38.                 q.emplace(t, p.second + 1);
  39.                 // 反转
  40.                 t = p.first;
  41.                 t[i] = trans(t[i], false);
  42.                 q.emplace(t, p.second + 1);
  43.             }
  44.         }
  45.         return -1;
  46.     }
  47. };

练习：

蓝桥杯 青蛙跳杯子【第八届】【省赛】