BFS 算法框架
从整体到细节，自顶向下，从抽象到具体的框架思维是通用的，不只是学习数据结构和算法，学习其他任何知识都是高效的。
# BFS 解决的问题
BFS 原本是图的一种遍历方式，从一个点开始，向四周开始扩散。一般都是用队列辅助遍历过程，每次将一个节点周围的所有节点加入队列。 因此广泛用于给定起始点（的条件）寻找最短距离。
BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多。
# BFS 算法框架
下面是用 C++ 写的一个框架，基本思想来源于 labuladong。
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node end)
{
deque<Node> q; // 核心数据结构
set<Node> vistied; // 避免走回头路
q.push_back(start);
visited.insert(start);
while(!q.empty())
{
int sz = q.size(); // 当前层的节点个数
// 当前队列中所有节点向四周扩散
for(int i = 0; i < sz; ++ i)
{
Node cur = q.front();
q.pop_front();
// 划重点：这里判断是否到达 target
if(cur is target)
return step;
// 将 cur 的相邻节点加入队列
for(Node x: cur.adj())
if(x not in visited)
{
q.push_back(x);
visited.insert(x);
}
}
}
// 划重点：在这里更新步数
++ step;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 应用例子
求二叉树的最小深度，打印二叉树以及打开转盘锁都可以用 BFS 框架来解决。