宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。
与DFS不同的是，DFS是一条路走到黑，而BFS则是一层一层搜索，这样的一种好处是可以找到最短路径。
BFS使用队列(queue)来实施算法过程，队列(queue)有着先进先出FIFO(First Input First Output)的特性，BFS操作步骤如下：
1、把起始点放入queue；
2、重复下述2步骤，直到queue为空为止：
1) 从queue中取出队列头的点；
2) 找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入queue中。
下面结合一个图(graph)的实例，说明BFS的工作过程和原理：
第一步：将起始节点1放入队列中，标记为已遍历：
第二步：从queue中取出队列头的节点1，找出与节点1邻接的节点2,3，标记为已遍历，然后放入queue中。
第三步：从queue中取出队列头的节点2，找出与节点2邻接的节点1,4,5，由于节点1已遍历，排除；标记4,5为已遍历，然后放入queue中。
第四步：从queue中取出队列头的节点3，找出与节点3邻接的节点1,6,7，由于节点1已遍历，排除；标记6,7为已遍历，然后放入queue中。
第五步：从queue中取出队列头的节点4，找出与节点4邻接的节点2,8，2属于已遍历点，排除；因此标记节点8为已遍历，然后放入queue中。
第六步：从queue中取出队列头的节点5，找出与节点5邻接的节点2,8，2,8均属于已遍历点，不作下一步操作。
第七步：从queue中取出队列头的节点6，找出与节点6邻接的节点3,8,9，3,8属于已遍历点，排除；因此标记节点9为已遍历，然后放入queue中。
第八步：从queue中取出队列头的节点7，找出与节点7邻接的节点3, 9，3,9属于已遍历点，不作下一步操作。
第九步：从queue中取出队列头的节点8，找出与节点8邻接的节点4,5,6，4,5,6属于已遍历点，不作下一步操作。
第十步：从queue中取出队列头的节点9，找出与节点9邻接的节点6,7，6,7属于已遍历点，不作下一步操作。
最后：queue为空，BFS遍历结束。
总结：
通过图示，可以很容易理解BFS的工作机制，在这里为大家准备了yxc大佬的BFS模板，喜欢的朋友可以点赞收藏一下：
制作不易，大佬们帮忙点个赞[送心]
还没有评论，来说两句吧...