之前看过的 BFS(Breadth First Search), 最近遇到类似问题时却没有想起. 在此再回顾一下, 并留下记录. 好记性毕竟不如坏笔头.
来由
在一些图的问题中, 经常遇到查找最长或最短路径、节点是否可达等与路径相关的问题时都可以结合 BFS 算法找到解决方法.
理念
BFS 的理念如其姓名, 广度优先又可以看作树里的层序遍历, 以 广度优先 的方式遍历整个图也就是按层优先的方式遍历, 找到符合条件的节点.
实现广度优先搜索, 需要结合队列实现层序遍历的顺序, 即优先遍历同一层节点, 下层的节点需要等上一层遍历完了再遍历.
例子
| 查找 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 算法不仅用在图的问题上, 其他类似路径的问题也能转化为图的问题. 比如查找二叉树中两个节点的最长或最短路径问题等.
还需要注意如果一个节点同时被多个节点指向, 需要做去重处理.
