[算法入门]——广度优先搜索（BFS）

广度优先搜索

广度优先搜索，也就是BFS（Breadth First Search），又称宽度优先搜索（不过这个才是正式名称吧）。BFS不像DFS，DFS是在一条路上越走越远，稍有不慎便有放飞自我的可能，而BFS是将当前节点附近的节点全部访问一遍，再去访问下一个节点附近的节点。这么听来可能会有点拗口，不过我们先画一张图来便于理解：画图.exe

你从1点出发，目标是遍历所有的节点。你先将1点添加到队列中（红色），然后依次遍历1点旁边的邻居（附件节点），将其添加到队列中：

然后，你再依次遍历2节点的邻居，但是2节点附近的1节点和3节点已经被添加到队列中，所以不予添加节点。

依次访问完1、2、3、4后，发现节点5附近还有一个节点6，于是也将6添加到已访问。

而所有节点访问所需要的最短路径如下图：

看上去很简单，我们只需要依次遍历所有已经访问过的节点，再将已经访问过的节点的邻居加入到队列中。

在BFS中有一个重要的数据结构：队列。那么，什么是队列呢？

队列好比生活中的队伍，保持着先进先出的思想。下图是一个没有节点的队列：

步骤1，在刚才举的例子中，我们先将1节点添加到队列中：

步骤2，随后，我们获取队列中的第一个元素，将它的邻居添加到队列中：

步骤3，我们弹出（类似删除）队首元素：

重复步骤2和步骤3的行为，直到队列为空。

或许会发现，有没有可能一个节点被反复添加到队列中，导致死循环呢？这种情况是务必避免的。我们可以引入一个数组vis，如果i节点被添加过，于是vis[i] = 1（表示已经入过队），这要只需要在添加节点的过程中，判断该节点是否进过队列。

大致模板：

 1 void BFS()
 2 {
 3     初始化，添加开始节点（例如1）
 4     while (队列不为空) 
 5     {
 6         获取队首元素，将vis设置为1    //保险 
 7         for (遍历该元素所有邻居)
 8         {
 9             if(该邻居进过队)
10             {
11                 入队，将vis设置为1 //保险 
12             }
13         }
14         弹出队首元素 
15     }
16 }

可能说得不好理解，所以这里给出一份流程图让大家慢慢琢磨：

这里再强调一下，邻居入队时要判断该邻居是否已经入过队，并且每次循环最后一定要弹出队首元素。不过，或许有人发现了——为什么DFS有回溯，但是BFS却不用回溯呢？DFS所得出来的每一个解，都不一定是最优解，所以需要回溯。但是BFS的特性已经保证所得出的解是最优解，除非你写错了。但是证明这一点非常困难，需要很长篇幅，而且BFS不能处理一些例外的题目，比如带边权图。

我们针对刚才的例子，来写一份从1到达所有节点所需步数的代码：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>//队列 
 4 using namespace std;
 5 struct Edge
 6 {
 7     int next, to;
 8 }edge[200];
 9 int EdgeNum = 0;//边的数量
10 int head[100]; 
11 void Add(int from, int to)
12 {
13     EdgeNum++;
14     edge[EdgeNum].next = head[from];
15     edge[EdgeNum].to = to;
16     head[from] = EdgeNum;
17 }
18 int vis[100], num[100];
19 /***主体部分，其他可省略不看***/
20 //变量说明：edge->边，vis->是否入过队，num->所需步数
21 void BFS()
22 {
23     memset(vis, 0, sizeof(vis));//0代表未入队 
24     memset(num, 0, sizeof(num));//所需要的的步数 
25     //队列，存储索引 
26     queue<int> q;
27     //入队  
28     q.push(1);
29     while(!q.empty())//队列不为空
30     {
31         int front = q.front();//获取队首元素
32         vis[front] = 1;//记录为入过队 
33         for (int i = head[front];i;i = edge[i].next)//遍历该节点的邻居 
34         {
35             int to = edge[i].to;//获取邻居节点的索引（这样写方便阅读，可省略）
36             if (vis[to] == 0)//如果未入队
37             {
38                 q.push(to);//将该邻居入队 
39                 vis[to] = 1;//记录为入过队 
40                 num[to] = num[front] + 1;//更新所需步数 
41             }
42         }
43         q.pop();//注意，必须出队！没写的话会一直死循环到世界末日 
44     }
45 }
46 /***主体部分，其他可省略不看***/
47 int main()
48 {
49     //n->节点数，q->边数 
50     int n, q;
51     cin >> n >> q;
52     //建边
53     for (int i = 1;i <= q;i++)
54     {
55         int u, v;
56         cin >> u >> v;
57         Add(u, v);
58         Add(v, u);
59     }
60     BFS();
61     //打印结果
62     for (int i = 1;i <= n;i++)
63         cout << num[i] << " "; 
64     return 0;//华丽结尾 
65 }

引入例题

快乐的讲解例题时间又到了~(≧▽≦)/~

这里引入的是洛谷P1135 奇怪的电梯（话说是哪个人可以想到这么奇怪的电梯的）

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $\le i \le N)(1≤i≤N)上有一个数字K_i(0 \le K_i \le N)Ki(0≤Ki≤N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3, 3 ,1 ,2 ,53,3,1,2,5代表了K_i(K_1=3,K_2=3,…)Ki(K1=3,K2=3,…)，从11楼开始。在11楼，按“上”可以到44楼，按“下”是不起作用的，因为没有-2−2楼。那么，从AA楼到BB楼至少要按几次按钮呢？$

输入格式

共二行。

第一行为

第二行为 $NN个用空格隔开的非负整数，表示K_iKi。$

输出格式

一行，即最少按键次数,若无法到达，则输出

输入输出样例

输入 #1

5 1 5

3 3 1 2 5

输出 #1

不过经过我的实际尝试，这道题可以用DFS写。但是为了不砸自己场子，先讲讲如何用BFS写。

这道题就是一个十分经典的最短路的问题。作为一道黄题，不是很难，但是很香（BB啥快讲啊）。

我们先大致整理一下，每一层楼的邻居是谁？在这道题中，每层楼有至多两个邻居，分别是向上走的楼层和向下走的楼层。当然，题目中有一个隐含限制条件：每层楼必须在1~N之间。换句话说，如果这个邻居层数超过N或小于1，那么这个邻居就是不可用的，就不能添加到队列中。

将这个限制条件加上vis来判断是否访问过，就可以很好解决这个问题了：

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 const int SIZE = 10000;
 5 int N, A, B, 
 6 k[SIZE],//电梯上的数字 
 7 vis[SIZE],//这里有没有走过 
 8 num[SIZE];//到每一层所需要的次数 
 9 int BFS()
10 {
11     queue<int> q;//队列，记录电梯的索引（层数）
12     q.push(A);
13     num[A] = 0;
14     while(!q.empty())
15     {
16         int front = q.front(); //front代表层数 
17         vis[front] = 1;
18         if (front == B)//确认过眼神，你就是B层！
19             return num[B]; 
20         int up = front + k[front], down = front - k[front];//up代表向上走所到的层数，down代表朝下走所到的层数
21         //如果所到的楼层在1-N之间，且没有被走过 
22         if (up >= 1 && up <= N && !vis[up]) vis[up] = 1, q.push(up), num[up] = num[front] + 1;
23         if (down >= 1 && down <= N && !vis[down]) vis[down] = 1, q.push(down), num[down] = num[front] + 1;
24         q.pop();//出队 
25     }
26     return -1;//到头没找到B层_(:з」∠)_ 
27 }
28 int main()
29 {
30     cin >> N >> A >> B;//输入N，A，B 
31     for (int i = 1;i <= N;i++)
32         cin >> k[i];//每层楼上的数字 
33     //开启你的BFS之旅
34     cout << BFS();//打印结果
35 }

484非常简单？其实可以有一点点优化，比如在22行和23行中，我们可以发现，如果电梯朝上走的话，就一定不会小于1，朝下走的话就一定不会大于N，所以可以删去大约14个字符（有必要这么斤斤计较吗）。这道题还可以用DFS来写，但是代码是我很久以前写的，或许很多地方没写清（关键是没打注释）

 1 #include <cstdio>
 2 int n, a, b, k[205], to[205] = {}, yes = 0x7ffffff;
 3 int x (int cing, int cs)
 4 {
 5     if (cs > yes)
 6         return 0;
 7     if (cing == b)
 8         if (yes > cs)
 9             yes = cs;
10     to[cing] = 1;
11     if(cing + k[cing] <= n && !to[cing + k[cing]])
12     {    
13         x(cing + k[cing], cs + 1);
14     }
15     if(cing - k[cing] > -1 && !to[cing - k[cing]])
16     {
17         x(cing - k[cing], cs + 1);
18     }
19     to[cing] = 0;
20 }
21 int main ()
22 {
23     scanf ("%d%d%d", &n, &a, &b);
24     for (int i = 1;i <= n;i++)
25     {
26         scanf ("%d", &k[i]);
27         to[i] = 0;
28     }
29     to[a] = 1;
30     x (a, 0);
31     if (yes != 0x7ffffff) 
32         printf ("%d", yes);
33     else
34         printf ("-1"); 
35 }

用深搜写啦

BFS与DFS的区别，以及优缺点

BFS在本质上和DFS一样，都是暴力算法，暴力求解。而且泛用性很广。许多题目都可以用BFS或DFS骗上20、30甚至50分，但是BFS与DFS往往会是空间或时间开销很大，甚至无法控制。

BFS与DFS的区别，通俗点来说，BFS就是浪费空间来获取时间上的优势，比如一张10*10的平面图，BFS起码需要一个二维数组来存储，并且使用100单位的内存。DFS就是浪费时间来节省空间，就像刚才的10*10的平面图一样，DFS最多需要40单位的内存，如果有优化甚至只需要20单位，但是时间开销极大，因为同一个节点会被访问许多次。

BFS

优点：速度相对来说会快很多，并且可以暴力做出许多题目。

缺点：但是遇到数据刁钻的情况，就得不到用武之地。而且没有做好优化就MLE让你怀疑人生。速度不一定会比DFS快。一道非常经典的题目“埃及分数”就很难用BFS做出来，就算做出来了空间开销也无法让人承受（评测姬：我太难了）。

DFS

优点：空间开销很小，并且思路容易想到，在有剪枝优化或记忆化搜索之后，可以很轻松做出许多题目。

缺点：太慢了，太慢了，太慢了！动不动就return 3221225725（栈溢出），数据大（超过100左右）那么一点点就挂了。