算法和数据结构4.2广度优先搜索

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

search.png

步骤

标记A为起点，G为终点。一开始在起点A上，并不知道G的位置。

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

从后补顶点中选出一个顶点。优先选择最早成为后补顶点的那个顶点，如果多个顶点同事成为候补的那个顶点，可以取后补顶点中的任意一个。

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

先搜索A，A不是顶点G（终点），将A标记为已搜索状态。

接下来搜索顶点此时B变为正在被搜索的顶点，同时B可以直达的未搜索的顶点将变成候补顶点。

B从候补顶点中移除.（这里的移除可以用队列的数据结构来实现，因为队列的特点是是先进先出的FIFO）

E和F也变成候补顶点。

开始搜索B，B不是顶点G(终点)，将B标记为已搜索状态。。

此时最早成为候补顶点的是C和D,于是选择C成为正在被搜索的顶点。

C从候补顶点中移除。

H被加入成为新的候补顶点。

开始搜索C，C不是顶点G（终点），将C标记为已搜索状态.

接下来候补顶点中D是最早成为候补顶点的，开始将D变为正在搜索的顶点.

将D从候补顶点中移除。

I和J被加入成为候补顶点。

开始搜搜D，D不是顶点G(终点)，将D标记为已搜索的状态。

依次类推

...

...

综述：从A搜索到G的广度优先搜索顺序为A、B、C、D、E、F、H、I、J、K、G

广度优先搜索的特征是从起点开始，由远及近进行广泛的搜索。因此，目标顶点离起点越近，搜偶所结束的越快。

上图是没有闭环的图。如果图中有闭环，搜索步骤也是一样的。上图中没有闭环的图叫做”树“。