广度优先遍历(Breadth First Search)的主要思想是：类似于树的层序遍历。

无向图的广度优先遍历图解：

从A开始，有4个邻接点，“B，C，D，F”，这是第二层；

在分别从B，C，D，F开始找他们的邻接点，为第三层。以此类推。

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

有向图的广度优先遍历图解：

与无向图类似 。可以参考。

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

代码实现

可参考《计算机考研机试攻略》部分：http://www.noobdream.com/Major/article/131/

课后习题

【2013年真题】若对如下无向图进行遍历，则下列选项中，不．是广度优先遍历序列的是（）

A. h，c，a，b，d，e，g，f        B. e，a，f，g，b，h，c，d 
C. d，b，c，a，h，e，f，g         D. a，b，c，d，h，e，f，g

参考答案：D
答案解析：D 选项是深度优先遍历不是广度优先遍历的顺序。 

【2012年真题】对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。
A．O(n) 
B．O(e) 
C．O(n+e) 
D．O(n*e) 

参考答案：C
答案解析：考查不同存储结构的图遍历算法的时间复杂度。 
广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为 O(e)，算法总的时间复杂度为 O(n+e)。