算法概念

也称宽度优先搜索，顾名思义，就是将一棵树一层一层往下搜。算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。BFS是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，还一定是路径最短的解。但是它盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。需要保存所有扩展出的状态，占用的空间大

在程序实现 BFS 时需要考虑以下问题：

• 队列：用来存储每一轮遍历得到的节点；
• 标记：对于遍历过的节点，应该将它标记，防止重复遍历。

BFS可用于解决2类问题：

• 从A出发是否存在到达B的路径；
• 从A出发到达B的最短路径(这个应该叫最少步骤合理)；

框架

1
2
3
4
5
6
7
8
9

BFS()
{
初始化队列
while(队列不为空且未找到目标节点)
{
取队首节点扩展，并将扩展出的节点放入队尾；
必要时要记住每个节点的父节点；
}
}

例题

1. 计算在网格中从原点到特定点的最短路径长度
2. 组成整数的最小平方数数量
3. 最短单词路径

https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E6%90%9C%E7%B4%A2.md

FROM :blog.cfyqy.com | Author:cfyqy