广度优先遍历（BFS）

广度优先遍历（Breadth-First-Search,BFS)要点：

1.找到与一个顶点相邻的所有顶点·

2.标记哪些顶点被访问过

3.需要一个辅助队列

• FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x,则返回-1。
• NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。

遍历序列的可变性

①使用邻接矩阵表示的图的广度优先遍历序列唯一

②使用邻接表表示的图的广度优先遍历序列不唯一

对于无向图，调用BFS函数的次数=连通分量数

bool visited[Max_VERTEX_NUM];           //访问标记数组
void BFSTraverse(Graph G){              //对图G进行广度优先遍历
    for(int i=0;i=0;w=NextNeighbor(G,v,w)){
            //检测v所有邻接点
            if(!visited[w]){            //w为v的尚未访问的邻接点
                visit(w);               //访问顶点w
                visited[w] = true;      //对w做已访问标记
                EnQueue(Q,w);           //顶点w入队列
            }
        }
    }
}

空间复杂度：最坏情况，辅助队列大小为O(|V|)

邻接矩阵存储的图：

访问|V|个顶点需要O(|V|)的时间

查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点

时间复杂度=O(|V|2)

邻接表存储的图：

访问|V|个顶点需要O(|V|)的时间

查找各个顶点的邻接点共需要O(|E|)的时间，

时间复杂度=O(|V|+|E|)

广度优先生成树：

由广度优先遍历确定的树；

邻接表存储的图的表示方式不唯一，遍历序列、生成树也不唯一；

遍历非连通图可得广度优先生成森林