广度优先搜索算法BFS

BFS 解决什么问题

广度优先搜索，一般用来解决最短路径的问题。DFS 解决连通性问题。

广度优先的搜索可以同时从起始点和终点开始进行，称之为双端 BFS。这种算法往往可以大大地提高搜索的效率。

算法思想

和深度优先搜索不同，广度优先的搜索是从起始点出发，一层一层地进行，每层当中的点距离起始点的步数都是相同的，利用这个性质来计算步数从而找到最短路径，当找到了目的地之后就可以立即结束。

DFS 更像一种一条路走到黑算法。BFS 是步步为营算法。

举例说明

依赖队列（Queue），先进先出（FIFO）。

第一步，选择一个起始顶点

第二步，从队列的头取出顶点 A，同时将与它相连的尚未被访问过的点按照字母大小顺序压入队列，同时把它们都标记为访问过，防止它们被重复地添加到队列中。（这一步和 dfs 类似但是接下来弹出的方式不一样）

第三步，先进先出先执行这一轮压入的节点即同一层级，后进先出先执行下一轮压入的节点即一条路径。

例题分析

假设从起始点 A 走到目的地 B 的过程中，最多允许打通 3 堵墙，求最短的路径的步数。（这个题目可以扩展到允许打通任意数目的墙。

重点在新的路径的新字，打通墙会带来新路径，检查新路径即可。