图的广度优先搜索遍历（BFS）类似于树的层次遍历。它的基本思想是：首先访问起始顶点v，然后选取与v邻接的全部顶点w₁，…，w_n进行访问，再依次访问与w₁，…，w_n邻接的全部顶点（已经访问过的除外），以此类推，直到所有顶点都被访问过为止。

广度优先搜索遍历图的时候，需要用到一个队列（二叉树的层次遍历也要用到队列），算法执行过程可简单概括如下：

1）任取图中一个顶点访问，入队，并将这个顶点标记为已访问；

2）当队列不空时循环执行：出队，依次检查出队顶点的所有邻接顶点，访问没有被访问过的邻接顶点并将其入队；

3）当队列为空时跳出循环，广度优先搜索即完成。

以邻接表为存储结构的广度优先搜索遍历算法如下：(www.daowen.com)

说明：对于图的广度优先搜索，可以对应之前已经掌握的二叉树的层次遍历来理解记忆，两者除了在有无visit[]访问标记数组上存在不同外，其他都十分类似。

以上两种遍历方法是针对连通图的。对非连通图进行遍历，只需将上述遍历函数放在一个循环中，循环用来检测图中的每一个顶点，如果当前顶点没有被访问，则调用上述函数从这个顶点遍历，否则什么也不做。

（1）深度优先搜索遍历

（2）广度优先搜索遍历

说明：上面介绍的两种遍历方式的代码描述，需要在理解的基础上达到能够熟练默写的程度，因为遍历操作是本章中其他一切操作的基础，也是考研中的重中之重。