广度优先遍历（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<G.vexnum;++i){    
        visited[i] = false;             //访问标记数组初始化
    }
    InitQueue(Q);                       //初始化辅助队列
    for(int i = 0;i < G.vexnum;++i){    //从0号顶点开始遍历
        if(!visited[i]){                //对每个连通分量都调用一次BFS
            BFS(G,i);                   //vi未访问过，从vi开始BFS
        }
    }
}
//广度优先遍历
void BFS(Graph G,int v){                //从顶点v出发，广度优先遍历图G
    visit(v);                           //访问初始顶点v
    visited[v] = true;                  //对v做已访问的标记
    Enqueue(Q,v);                       //顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);                   //顶点v出队列
        for(w=FirstNeighbor(G,v);w>=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|)

广度优先生成树：

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

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

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