从图中任一顶点v出发遍历图的BFS算法的描述:

 1  访问顶点v并打上标记;

 2  依次访问顶点v的未访问的邻接点，再访问与这些邻接点相邻接且未访问的顶点。

 3  若图中还有顶点未被访问，则另选一个未访问的顶点，重新开始上述过程。

宽度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。

对下图，从顶点0出发BFS遍历，其遍历序列是：

    0,1,11,10,2,5,6,9,3,4,7,8。

宽度优先搜索算法要实现按层次访问，需要一个队列来保存已访问过但其邻接点尚未考察的顶点。

 (1)访问0，0入队,(0)。

 (2)0出队,( )，访问与0相关联的未访问顶点，访问一个入队一个，(1,11,10)。

 (3)重复，直到队列空。

 若图中还有顶点未被访问，则另选一个未访问的顶点，重新开始上述过程。

 图中顶点以及遍历时生成的边所构成的子图称为宽度优先搜索生成树。

BFS算法的特点

1、每个顶点进出队列各一次。

2、对于每个出队的顶点，都要检查其所有的邻接点，对于无向图每条边被检查2次。

3、n个顶点，e条边的图采用邻接表存储，BFS算法的时间为O(n+e),而采用邻接矩阵表示，时间为O(n2)。

如同二叉树的遍历算法，图的DFS和BFS算法是最重要、最基本的算法，许多有关图的算法都可以对它们稍加修改得到。例如，求无向图的连通分量、有向图的强连通分量、生成树(森林)等。