宽度优先

一.宽度优先搜索（BFS）是什么？

百度百科这样说：

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

过于理论性，不过说出了核心：

它是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。**并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。**

也有人这样说：

就是从根结点位置开始遍历，遍历结束后依次遍历与根节点相邻的点，相邻点遍历结束后继续遍历上轮第一个遍历结点的相邻的未遍历的点，直至所有的点都遍历结束。

这个说的比较好，但仍然有一点生硬。

简单来说，就是：

宽度优先搜索是一种对图进行搜索的算法。假设我们一开始位于某个顶点（即起点），此 时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到到达指定顶点（即终 点）。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点 近的顶点开始搜索。

下面，我将用步骤图的方式，向大家介绍这种方法。

二.图解宽搜（BFS）

A为起点，G为终点。一开始我们在起点A上，此时并不知道G在哪里。

将可以从A直达的三个顶点B、C、D设为下一步的候补顶点。

从候补顶点中选出一个顶点。优先选择最早成为候补的那个顶点，如果多个顶点同时成为候补，那么可以随意选择其中一个。 （优先选择最早成为候补的那个顶点，这是一种“先进先出”的方式，后面会讲到）

此处 B、C、D 同时成为候补，所以我们随机选择了最左边的顶点B。

移动到选中的顶点B上。此时我们在B上， 所以B变为红色，同时将已经搜索过的顶点变为橙色。

此处，候补顶点是用“先入先出”（FIFO）的方式来管理的，因此可以使用“队列”这个数据结构。（这个结构将会在后面讲解，请往下翻）

将可以从B直达的两个顶点E和F设为候补 顶点。

此时，最早成为候补顶点的是C和D，我们选择了左边的顶点C。

移动到选中的顶点C上。

将可以从C直达的顶点H设为候补顶点。

重复上述操作直到到达终点，或者所有的顶点都被遍历为止。

这个示例中的搜索顺序为 A、B、C、D、E、F、 H、I、J、K。

完成了从A到I的搜索，现在在顶点J处。

到达终点G，搜索结束。

补充说明：由上可以知道，广度优先搜索的特征为从起点开始，由近及远进行广泛的搜索。因此，目标顶点离起点越近，搜索结束得就越快。