1. BFS遍历

BFS 算法的思想：对一个无向连通图，在访问图中某一起始顶点 v 后，由 v 出发，依次访问 v 的所有未访问过的邻接顶点 w1, w2, w3, …wt；然后再顺序访问 w1, w2, w3, …wt 的所有还未访问过的邻接顶点；再从这些访问过的顶点出发，再访问它们的所有还未访问过的邻接顶点， ……，如此直到图中所有顶点都被访问到为止。 

接下来以下图(a)所示的无向连通图为例解释 BFS 搜索过程。 假设在多个未访问过的邻接顶点中进行选择时，按顶点序号从小到大的顺序进行选择。

对上图(a)所示的无向连通图，采用 BFS 思想搜索的过程为：

1. 访问顶点 A，这是第一层；
2. 访问顶点 A 的 3 个邻接顶点 B、 D 和 E，这是第二层；
3. 访问顶点 B 的未访问过的邻接顶点（即顶点 C）， 访问顶点 D 的未访问过的邻接顶点（即  顶点 F），顶点 E 没有未访问过的邻接顶点，这是第三层；
4. 访问顶点 C 的未访问过的邻接顶点（即顶点 G）， 访问顶点 F 的未访问过的邻接顶点（即顶点 H），这是第四层；
5. 顶点 G 没有未访问过的邻接顶点，访问顶点 H 的未访问过的邻接顶点（即顶点 I），这是第五层。 

2. BFS 算法的实现 

与深度优先搜索过程一样，为避免重复访问，也需要一个状态数组 visited[n]，用来存储各顶点的访问状态。如果 visited[i] = 1，则表示顶点 i 已经访问过；如果 visited[i] = 0，则表示顶点 i 还未访问过。初始时，各顶点的访问状态均为 0。 

• 访问顶点 A，然后把顶点 A 入队列；
• 取出队列头的顶点，即顶点 A，然后依次访问顶点 A 的 3 个邻接顶点 B、 D 和 E，并把这 3 个顶点入队列；
• 取出此时队列头的顶点，即顶点 B， 然后访问顶点 B 的未访问过的邻接顶点， 即顶点 C，并把顶点 C 入队列；
• 取出此时队列头的顶点， 即顶点 D， 然后访问顶点 D 的未访问过的邻接顶点， 即顶点 F，并把顶点 F 入队列；
• 取出此时队列头的顶点，即顶点 E，而顶点 E 已经没有未访问过的邻接顶点；
• 取出此时队列头的顶点， 即顶点 C， 然后访问顶点 C 的未访问过的邻接顶点， 即顶点 G，并把顶点 G 入队列； 
• 取出此时队列头的顶点， 即顶点 F， 然后访问顶点 F 的未访问过的邻接顶点， 即顶点 H，并把顶点 H 入队列；
• 取出此时队列头的顶点，即顶点 G，而顶点 G 已经没有未访问过的邻接顶点；
• 取出此时队列头的顶点，即顶点 H，然后访问顶点 H 的未访问过的邻接顶点，即顶点 I，并把顶点 I 入队列；
• 取出此时队列头的顶点，即顶点 I，而顶点 I 已经没有未访问过的邻接顶点；至此，队列为空， BFS 搜索执行完毕。

BFS 执行过程中，各顶点的访问顺序依次为： A→B→D→E→C→F→G→H→I 。

如果用邻接表存储图，则 BFS 算法实现的伪代码如下： 

BFS( 顶点 i ) //从顶点 i 进行广度优先搜索
{
    visited[ i ] = 1; //将顶点 i 的访问标志置为 1
    将顶点 i 入队列;
    while( 队列不为空 )
    {
        取出队列头的顶点，设为 k
        p = 顶点 k 的边链表表头指针
        while( p 不为空 )
        {
            //设指针 p 所指向的边结点所表示的边的另一个顶点为顶点 j
            if( 顶点 j 未访问过 )
            {
                将顶点 j 的访问标志置为 1
                将顶点 j 入队列
            }
            p = p->nextarc; //p 移向下一个边结点
        } //end of while
    } //end of while
} //end of BFS

如果用邻接矩阵存储图（设顶点个数为 n），则 BFS 算法实现的伪代码如下： 

BFS( 顶点 i ) //从顶点 i 进行广度优先搜索
{
    visited[ i ] = 1; //将顶点 i 的访问标志置为 1
    将顶点 i 入队列;
    while( 队列不为空 )
    {
        取出队列头的顶点，设为 k
        for( j=0; j<n; j++ ) //对其他所有顶点 j
        {
            //j 是 k 的邻接顶点，且顶点 j 没有访问过
            if( Edge[k][j]==1 && !visited[j] )
            {
                将顶点 j 的访问标志置为 1
                将顶点 j 入队列
            }
        } //end of for
    } //end of while
} //end of BFS

3.  BFS 算法的复杂度分析 

设无向图有 n 个顶点，有 m 条边。

如果使用邻接表存储图， 对从队列头取出来的每个顶点 k， 首先要取出该顶点的边链表头指针，然后沿着该顶点的边链表中的每个边结点，把未访问过的邻接顶点入队列。在这个过程每个顶点访问各一次， 2m 个边结点各访问一次，所以总的时间代价为 O(n+2m)。

如果用邻接矩阵存储图，由于在邻接矩阵中只是间接地存储了边的信息，所以对从队列头取出来的每个顶点 k，要循环检测无向图中的其他每个顶点 j（不管是否与顶点 k 相邻），判断 j 是否跟 k 相邻且是否访问过；另外，每个顶点都要入队列，都要从队列头取出，进行判断，所以总的时间代价为 O(n²)。