C++笔记 算法篇5 —— 广度优先搜索
1. 广度优先搜索简介
广度优先搜索BFS（Breadth First Search）也称为宽度优先搜索，它是一种先生成的结点先扩展的策略。
在广度优先搜索算法中，解答树上结点的扩展是按它们在树中的层次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，……，对层次为n+1的任一结点进行扩展之前，必须先考虑层次完层次为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，可以按任意顺序来扩展它们。通常采用的原则是先生成的结点先扩展。
为了便于进行搜索，要设置一个表存储所有的结点。由于在广度优先搜索算法中，要满足先生成的结点先扩展的原则，所以存储结点的表一般采用队列这种数据结构。
2. 一般搜索步骤
（1）从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。
（2）检查新生成的结点，看它是否已在队列中存在，如果新结点已经在队列中出现过，就放弃这个结点，然后回到第（1）步。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。
（3）检查新结点是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展。
最终可能产生两种结果：找到目标结点，或扩展完所有结点而没有找到目标结点。
如果目标结点存在于解答树的有限层上，广度优先搜索算法一定能保证找到一条通向它的最佳路径，因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径，则要保存每个结点的来源，也就是它是从哪一个节点扩展来的。
对于广度优先搜索算法来说，问题不同则状态结点的结构和结点扩展规则是不同的，但搜索的策略是相同的。
对于不同的问题，用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否为目标结点和是否为重复结点的判断等方面则有所不同。对具体的问题需要进行具体分析，这些函数要根据具体问题进行编写。
可能对于上面的讲解，大家还不是很了解什么是广度优先搜索，下面我们通过一个例子再来聊一聊什么是广度优先搜索。假设你自己经营了一家巧克力工厂，你需要找到巧克力销售商，这样你的巧克力才能卖出去。因此，你首先开始在你认识的朋友里面寻找，有没有巧克力销售商。如下图所示，你一共有三个好朋友，分别是马小云、刘小东和马小腾。
一开始的的查找很简单，你只需要创建一个朋友们的名单。然后依次检查名单中的每一个人，看看他是不是巧克力销售商。
首先，你开始查找你的朋友马小云，如果他是巧克力销售商，那么大功告成，查找也就结束了，如果他不是的话继续查找第二个朋友刘小东，同样如果他是巧克力销售商，那么大功告成，查找也就结束了，如果他不是的话继续查找第三个朋友马小腾，如果他是巧克力销售商，那么大功告成，查找也就结束了，如果他不是的话就表示你的朋友里面没有巧克力销售商。那接下来怎么办呢？很显然，接下来你就需要在查找你朋友的朋友有没有巧克力销售商了。
同样，你需要首先把朋友的朋友的名单加入列表中，然后再一个个查找他们是否为巧克力销售商。这样一来，你不仅在朋友中查找，还在朋友的朋友中查找。别忘了，你的目标是在你的人际关系网中找到一位巧克力销售商。因此，如果马小腾不是巧克力销售商，就将其朋友也加入到名单中。这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个人际关系网，直到找到巧克力销售商。这就是广度优先搜索算法。
3. 广搜的问题解决范围
第一类问题： 从节点A出发，有前往节点B的路径吗？（在你的人际关系网中，有巧克力销售商吗？） 第二类问题： 从节点A出发，前往节点B的哪条路径最短？（哪个巧克力销售商与你的关系最近？） 刚才你看到了如何回答第一类问题，下面来尝试回答第二类问题——谁是关系最近的巧克力销售商。例如，朋友是一度关系，朋友的朋友是二度关系。
在你看来，一度关系胜过二度关系，二度关系胜过三度关系，以此类推。因此，你应先在一度关系中搜索，确定其中没有巧克力销售商后，才在二度关系中搜索。广度优先搜索就是这样做的！在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。顺便问一句：将先检查刘小东还是雷小军呢？刘小东是一度关系，而雷小军是二度关系，因此将先检查刘小东，后检查雷小军。你也可以这样看，一度关系在二度关系之前加入查找名单。
你按顺序依次检查名单中的每个人，看看他是否是巧克力销售商。这将先在一度关系中查找，再在二度关系中查找，因此找到的是关系最近的巧克力销售商。广度优先搜索不仅查找从A到B的路径，而且找到的是最短的路径（貌似这里又有一点贪心的感觉了）。
注意，只有按添加顺序查找时，才能实现这样的目的。换句话说，如果马小云先于雷小军加入名单，就需要先检查马小云，再检查雷小军。如果马小云和雷小军都是巧克力销售商，而你先检查雷小军再检查马小云，结果将如何呢？找到的巧克力销售商并非是与你关系最近的，因为雷小军是你朋友的朋友，而马小云是你的朋友。因此，你需要按添加顺序进行检查。有一个可实现这种目的的数据结构，那就是队列（queue），所以这也就是我们之前学习队列知识的原因所在。
例题1：寻宝
小萱萱参加了一个“寻宝”游戏:在一排均匀排列的树上，被随机放置了一个“宝贝”，看谁能以最少的时间找到这个“宝贝”。每一个寻宝的人开始会站在第N(0≤N≤100000)棵树边，假设树有100000 棵，“宝贝”被放在第K(0≤K≤100000)棵树上，寻宝人有两种移动办法:步行和跳跃。假如寻宝人现在在第X棵树边，步行每秒可以从第X棵树向第X-1棵和第X+1棵树走去，跳跃可以让她在1秒内从第X棵树直接跳到第2*X棵树边(假如他有超能力完成跳跃，跳跃过.程中不能超过树的边界)。现在要求找到“宝贝”需要的最短时间。
输入格式： 仅有两个整数N和K。
输出格式： 最短时间
输入样例：
5 17输出样例：
4解题思路： 首先我们明确这是广度优先搜索的第二类问题，即从节点A出发，前往节点B的哪条路径最短？在本题中即从开始的树n开始，最少需要经过几次就可以找到第k棵树上的宝贝。我们首先从第n棵树出发，对于每一棵树，都有三种方式可以跳到下一棵树，即向前跳一步、向后跳一步和向后2倍距离跳。我们借用样例输入和输出来模拟下这个广度优先搜索的过程。
第1次搜索：5向三个方向搜索，分别是4,6,10；4,6,10进入队列，5出队列
第2次搜索：4向三个方向搜索，分别是3,5,8，去掉5；
6向三个方向搜索，分别是5,7,12，去掉5；
10向三个方向搜索，分别是9,11,20；
3,8,7,12,9,11,20进入队列，4,6,10出队列；
第3次搜索：3向三个方向搜索，分别是2,4,6，去掉4和6；
8向三个方向搜索，分别是7,16,9，去掉7和9；
7向三个方向搜索，分别是6,8,14，去掉6和8；
12向三个方向搜索，分别是11,13,24；
9向三个方向搜索，分别是8,10,18，去掉8和10；
11向三个方向搜索，分别是10,12,22，去掉10；
20向三个方向搜索，分别是19,21,40；
2,16,11,13,24,18,12,22,19,21,40进入队列，3,8,7,12,9,11,20出队列；
第4次搜索：2向三个方向搜索，分别是1,3,4，去掉3和4；
16向三个方向搜索，分别是15,17,32；
这个时候我们发现已经找到目标节点了，即编号为17的这棵树，并且通过了4次搜索，因此找到“宝贝”需要的最短时间为4次。下面我们一起来用代码来模拟我们上面的这个过程。
完整的代码如下所示：
#include <bits/stdc++.h>
using namespace std;
int t[100001], f[100001]; //数组t存储时间，数组f标记该树有没有跳过
int n, k; //n表示开始位置，k表示结束位置
queue<int> shu; //定义队列shu
int bfs(int n) {
shu.push(n); //开始位置存入队列中
t[n] = 0, f[n] = 1; //一开始的时间为0，开始位置被标记为1
while (shu.empty() != 1) //当队列非空时开始循环
{
int x = shu.front(); //x为队列的队首元素
if (x == k) return t[x]; //如果队首等于结束位置，则表示找到了，返回时间
//如果没找到，分三种情况讨论，分别向前跳、向后跳和2倍向后跳
if (x - 1 >= 0 && f[x - 1] == 0) //如果x-1>=0即可以向前跳，且前面这个树还没有去过
{
shu.push(x - 1); //x-1进入队列
t[x - 1] = t[x] + 1; //时间加1
f[x - 1] = 1; //x-1被标记
}
if (x + 1 <= 100000 && f[x + 1] == 0) //如果x+1< =100000即可以向后跳，且后面这个树还没有去过
{
shu.push(x + 1); //x+1进队列
t[x + 1] = t[x] + 1; //时间加1
f[x + 1] = 1; //x+1被标记
}
if (x * 2 <= 100000 && f[x * 2] == 0) //如果x*2< =100000即可以向后2倍跳，且后面这个树还没有去过
{
shu.push(x * 2); //x*2进队列
t[x * 2] = t[x] + 1; //时间加1
f[x * 2] = 1; //x*2被标记
}
shu.pop(); //这个数已经被遍历完了，出队列
}
}
int main() {
cin >> n >> k;
cout << bfs(n); //从起点开始搜索
}
例题2：最少步数
在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100*100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。
输入格式： 两行，每行两个正整数，表示马所在的坐标。
输出格式： 两行，所走的最少步数。
样例输入：
12 16
18 10
样例输出：
8
9
解题思路： 对于这道题目，很显然对于每个棋子有很多种走法，在不越界且未走过的基础上搜索。我们先在草稿纸上看看，一共有多少种走法，很显然一共有12种走法。至于具体的代码，我想同学们应该可以独立完成了。
完整的代码如下所示：
#include <bits/stdc++.h>
using namespace std;
int dx[12] = { 1, 2, -1, -2, 1, 2, -1, -2, 2, -2, 2, -2 };
int dy[12] = { 2, 1, 2, 1, -2, -1, -2, -1, 2, 2, -2, -2 };
int x1, yy, x2, y2;
int a[101][101], f[101][101];
int bfs(int m, int n) {
queue<int> x, y;
x.push(m);
y.push(n);
memset(f, 0, sizeof(f));
memset(a, 0, sizeof(a));
a[m][n] = 0;
int sx = m,sy = n;
while (sx != 1 || sy != 1) {
for (int i = 0; i < 12; i++) {
sx = x.front() + dx[i], sy = y.front() + dy[i];
if (sx >= 1 && sx <= 100 && sy >= 1 && sy <= 100 && f[sx][sy] == 0)
a[sx][sy] = a[x.front()][y.front()] + 1,f[sx][sy] = 1,x.push(sx), y.push(sy);
}
x.pop(), y.pop();
}
return a[1][1];
}
int main() {
cin >> x1 >> yy >> x2 >> y2;
cout << bfs(x1, yy) << '\n' << bfs(x2, y2);
return 0;
}