来由

在一些图的问题中, 经常遇到查找最长或最短路径、节点是否可达等与路径相关的问题时都可以结合 BFS 算法找到解决方法.

理念

BFS 的理念如其姓名, 广度优先又可以看作树里的层序遍历, 以 广度优先 的方式遍历整个图也就是按层优先的方式遍历, 找到符合条件的节点.
实现广度优先搜索, 需要结合队列实现层序遍历的顺序, 即优先遍历同一层节点, 下层的节点需要等上一层遍历完了再遍历.

例子

查找 A -> H 的最短路径 流程
找到A->H的最短路径

搜索过程

当前队列 匹配情况
A A != H, 追加 A 的下层
B G C B != H, 追加 B 的下层
G C D G != H, 追加 G 的下层
C D H C != H, 追加 C 的下层
D H E D != H, 追加 D 的下层
H E F H == H, 满足条件, 搜索结束

总结

BFS 算法不仅用在图的问题上, 其他类似路径的问题也能转化为图的问题. 比如查找二叉树中两个节点的最长或最短路径问题等.
还需要注意如果一个节点同时被多个节点指向, 需要做去重处理.