BFS算法（广度优先搜索）——Python学习日记

欢迎大家来到IT世界,在知识的湖畔探索吧!

一、定义：广度优先搜索算法是最简便的图的搜索算法之一，属于一种盲目搜寻法。目的是系统地展开并检查图中的所有节点，来找寻结果。也就是说，它并不考虑结果的可能存在的位置，全面地搜索整个图，一直到找到结果为止。

二、核心思想：讲究的是搜索的广度，每条路都走一点，先把周边的走完，然后再去走更深的地方。

三、算法思路：

队列（先进先出）

1、首先创建一个空队列queue来存放节点和一个空的列表visit来存放已经访问的节点

2、依次将起始点和邻接点加入队列queue和列表visit中

3、pop出队列中最先进入的节点，并且从图中获取该节点的邻接点

4、如果邻接点不在列表visit中，就将该邻接点加入队列queue和列表visit中

5、输出pop出来的节点

6、重复步骤3、4、5，一直到队列为空。

四、算法实现：

def bfs（参数）：

初始化队列queue，visit

初始元素存入队列queue，visit

while（队列不空）

｛

出队列头元素

循环找到队头元素相邻的又同时没有被处理的节点进行进队处理，满足条件就入队，变更状态

可以顺便记录步数以及这个节点的父节点是谁。

｝

五、实现过程：

如图从A开始，使用BFS算法，输出查找路径

欢迎大家来到IT世界,在知识的湖畔探索吧!

1、A首先进队列queue。

queue=A，visit=空

2、接着A出队，这时候与A相邻的节点B，C，D进队。

queue=B，C，D

visit=A

3、接着B出队，与B相邻的A、E、F节点中，E、F没有进过队，所以E、F进队列queue。

queue=C，D，E，F

visit=A，B

4、接着C出队，与C相邻的A、D、F、G中，只有G没有入过队，所以G入队

queue=D，E，F，G

visit=A，B，C

5、接着D出队，与D相邻的A、C、G已经全部进过队列

queue=E，F，G

visit=A，B，C，D

6、接着E出队，相邻的B已经入过队

queue=F，G

visit=A，B，C，D，E

7、接着F出队，相邻的B、C已经入过队

queue=G

visit=A，B，C，D，E，F

8、最后G出队，与G相邻的C、D已经入过队

queue=空

visit=A，B，C，D，E，F，G

至此循环结束，BFS算法也就完成了全部遍历。