算法 | 广度优先遍历BFS

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

问题描述

BFS算法，也称作广度优先搜索算法。是一种图形搜索演算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。（百度百科）

举例分析：

先用一个树结构来说明bfs算法的搜索规律

如果上图要用bfs算法的话。它会从左至右遍历每层节点

遍历过程：A B C D E F G H I

实例练习

那如果是一个图呢？一样的原理，只是图没有根节点，所以我们要选取一个点来作根节点

以下图为例，我们以A做根节点，A的下一层为B C，假设距离为1，则距离A为2的作为下一层节点也就是D E,同理再下一层为F。则顺序为ABCDEF

接下来就是代码实现了：

因为BFS算法是一层一层的遍历，所以我们可以用一个队列来储存，接下来讲为什么

队列是先进先出的结构，我们可以先将一个起始节点塞入队列，然后每次拿出一个节点，并将它的邻接点塞入。

假设我们先塞入A，将其取出后塞入A的邻接点BC，接着取出B塞入B的邻接点D,依此类推。这样做可以保证层的队列顺序，比如这个队列的存入顺序就是ABCDEF

代码我们分三步写：输入，算法设计，输出

第一步输入：

因为我们需要记录的每一个节点以及与其相连的节点，所以可以用字典来存入

第二步算法设计：

我们需要用到的数据有两个，一个是地图数据，一个是根节点（也可以说是起点）

具体思路在代码旁作注释表达

第三步输出：

假设起始点也就是根节点是E，距离E一距离的是CD，相距二距离的是ABF

将起始点设为A来看看

符合BFS算法的遍历顺序。

结语

学习算法时，很容易存在逻辑不理解的地方，只要多练多看，一定会可以理解的。BFS算法不仅可以用来遍历，还可以用来获取路径，比如从A到F的最短路径，只需要在源代码的基础上略做修改，小伙伴们可以动动脑筋，自己下来试试哦。若有疑问，可在评论区留言。

where2 go 团队

   

微信号：算法与编程之美          

长按识别二维码关注我们!

温馨提示： 点击页面右下角 “写留言”发表评论，期待您的参与！期待您的转发！