广度优先搜索是一种对图进行搜索的算法，假设我们位于某个顶点（作为起点），此时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到达到指定顶点（终点）。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索。
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
广度优先搜索的特征是从起点开始，由远及近进行广泛的搜索。因此，目标顶点离起点越近，搜偶所结束的越快。
上图是没有闭环的图。如果图中有闭环，搜索步骤也是一样的。上图中没有闭环的图叫做”树“。
网友评论