广度优先遍历（BFS）算法详解

广度优先遍历（BFS）算法详解

宽度优先搜索（BFS，Breadth First Search）是一个针对图和树的遍历算法。该算法发明于上世纪50年代末60年代初，最初用于解决迷宫最短路径和网络路由等问题。

对于下面的树而言，BFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8。

BFS使用队列（queue）来实施算法过程，队列（queue）有着先进先出FIFO（First Input First Output）的特性。

BFS操作步骤如下：

1. 把起始点放入queue；
2. 重复下述2步骤，直到queue为空为止：
   1. 从queue中取出队列头的点；
   2. 找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入queue中。

下面结合一个图（graph）的实例，说明BFS的工作过程和原理：

（1）将起始节点1放入队列中，标记为已遍历：

（2）从queue中取出队列头的节点1，找出与节点1邻接的节点2,3，标记为已遍历，然后放入queue中。

（3）从queue中取出队列头的节点2，找出与节点2邻接的节点1,4,5，由于节点1已遍历，排除；标记4,5为已遍历，然后放入queue中。

（4）从queue中取出队列头的节点3，找出与节点3邻接的节点1,6,7，由于节点1已遍历，排除；标记6,7为已遍历，然后放入queue中。

（5）从queue中取出队列头的节点4，找出与节点4邻接的节点2,8，2属于已遍历点，排除；因此标记节点8为已遍历，然后放入queue中。

（6）从queue中取出队列头的节点5，找出与节点5邻接的节点2,8，2,8均属于已遍历点，不作下一步操作。

（7）从queue中取出队列头的节点6，找出与节点6邻接的节点3,8,9，3,8属于已遍历点，排除；因此标记节点9为已遍历，然后放入queue中。

（8）从queue中取出队列头的节点7，找出与节点7邻接的节点3, 9，3,9属于已遍历点，不作下一步操作。

（9）从queue中取出队列头的节点8，找出与节点8邻接的节点4,5,6，4,5,6属于已遍历点，不作下一步操作。

（10）从queue中取出队列头的节点9，找出与节点9邻接的节点6,7，6,7属于已遍历点，不作下一步操作。

（11）queue为空，则遍历结束