广度优先搜索算法

    上一篇简书小编分享了“深度优先搜索”算法，今天小编继续分享下“广度优先搜索”算法。

一、何为“广度优先搜索”

    广度优先搜索(Breadth First Search)是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了这种类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。

    它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

    换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2...的顶点。【类似于树的层次遍历】

二、广度优先搜索图解

1、无向图

G1

    该无向图额邻接矩阵如下：

G1邻接矩阵

    该无向图邻接表如下：

G1邻接表

    对上面的图G1进行深度优先遍历【使用队列辅助】：

    第1步：建立队列queue，，顶点ABCDEFG是按照顺序存储，所以先访问A，将A标记为已访问，同时加入对列queue。【A】

    第2步：此时队列不为空，队列中A出列，访问A的邻接点，即"B,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，B在"D和F"的前面，因此，先访问B，然后标记B为已访问，同时加入队列queue。【B】

    第3步：访问D(A的邻接点)。 在第2步访问B之后，接下来继续访问A的其它邻接点，即"D,F"中的一个。因此，先访问D，然后标记D为已访问，同时加入队列queue。【B、D】

    第4步：访问F(A的邻接点)。 在第4步访问D之后，接下来应该访问的A的最后一个邻接点F，然后标记F为已访问，同时加入队列queue。【B、D、F】

    第5步：此时A的邻接点已经全部访问并入列，接着从队列中取出”B”，访问B的邻接点”A和G”。A已经访问过，跳过，访问顶点G，标记G为已访问，然后加入队列queue。【D、F、G】

    第6步：此时B的邻接点已经全部访问过并入列，接着从队列中取出D，访问D的邻接点C，并标记C为已经访问，然后加入队列。【F、G、C】

    第7步：此时D的邻接点已经全部访问过并入列，接着从队列中取出F，访问F的邻接点H，并标记H为已经访问，然后加入队列。【G、C、H】

    第8步：此时F的邻接点已经全部访问过并入列，接着从队列中取出G，G的邻接点有”B、E和H”，”B”已经访问过，跳过。访问E，并标记E为已经访问，然后加入队列。而接下来的另一个邻接点H也已经访问过，故也跳过。【C、H、E】

    第9步：此时G的邻接点已经全部访问过并入列，接着从队列中取出C，C的邻接点为E，已经访问过跳过。【H、E】

    第10步：此时C的邻接点已经全部访问过并入列，接着从队列中取出H，H的邻接点为”F和H”，都已经访问过跳过。【E】

    第11步：此时H的邻接点已经全部访问过并入列，接着从队列中取出E，E的邻接点为”C和G”，都已经访问过跳过。【】

    第12步：此时队列为空，一次遍历结束。

    根据顶点标记为访问的顺序，可得访问顺序是：A -> B -> D-> F -> G -> C -> H -> E。

    其实这就是树的层序遍历，我们把这个图调整成一棵树的形状如下：

G1调整成树状图

    然后从上到下，从左往右进行遍历。

    由上图同样可得遍历顺序为：A -> B -> D-> F -> G -> C -> H -> E。

2、有向图

G2

    有向图的遍历方法同样如上所示，这里也就不分析了，这里只贴一个调整的树状图如下所示：

G2调整成树状图

    访问顺序是：A -> B -> D-> F -> G -> C -> H -> E。

三、代码实现

    这部分的代码是在之前小编写的邻接表的基础上继续添加代码实现的，邻接矩阵这里没有贴代码，大家可以自行分析。

C++实现的算法

    如有误请指正！