1.与树的广度优先遍历之间的联系
先回顾一下树的广度优先遍历也就是层序遍历。
1.树的广度优先遍历（队列）
- 若树非空，则根节点入队。
- 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队。
- 重复②直到队列为空。
2.图的广度优先遍历
- 找到与一个顶点相邻的所有顶点。
- 标记哪些顶点被访问过。
- 需要一个辅助队列。
注意：这里需要使用要: 图的基本操作中的查找邻接点和查找下一个邻接点的操作。
定义一个标记数组，记录每个顶点是否被访问过。
代码实现：
bool visited[MAX_VERTEX_NUM];//访问标记数组//广度优先遍历
void BFS(Graph G, int v) {//从顶点v出发，广度优先遍历图Gvisit(v);//访问初始顶点vvisited[v] = TRUE;//对v做已访问标记Enqueue(Q, v);//顶点v入队列Qwhile (!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);//访问顶点wvisited[w] = TRUE;//对w做已访问标记EnQueue(Q, w);//顶点w入队列}//if}// while
}
2.算法分析
值得一提的是：
- 同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一。
- 同一个图邻接表表示方式不唯一，因此广度优先遍历序列不唯一。
如果采用上述算法，若是图是非连通图，则无法遍历完所有结点。
解决方法：遍历完一轮后，重新访问标记数组，找到依旧为false的结点，再调用一次BFS。
修改后代码为：
bool visited[MAX_VERTEX_NUM];//访问标记数组void BFSTraverse(Graph G) {//对图G进行广度优先遍历for (i = 0; i < G.vexnum; ++i)visited[i] = FALSE;//访问标记数组初始化InitQueue(Q);//初始化辅助队列Qfor (i =; i < G.vexnum; ++i)//从0号顶点开始遍历if (!visited[i])//对每个连通分量调用一次BFSBFS(G, i);// vi未访问过，从vi开始BFS
}//广度优先遍历
void BFS(Graph G, int v) {//从顶点v出发，广度优先遍历图Gvisit(v);//访问初始顶点vvisited[v] = TRUE;//对v做已访问标记Enqueue(Q, v);//顶点v入队列Qwhile (!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);//访问顶点wvisited[w] = TRUE;//对w做已访问标记EnQueue(Q, w);//顶点w入队列}//if}// while
}
结论:对于无向图，调用BFS函数的次数=连通分量数.
3.复杂度分析
1.空间复杂度
最坏情况，辅助队列大小为O(IV|).
2.时间复杂度
- 邻接矩阵存储的图:访问个顶点需要OI)的时间，查找每个顶点的邻接点都需要O()的时间，而总共有||个顶点时间复杂度= O(IV|2)。
- 邻接表存储的图:访问个顶点需要O(V)的时间,查找各个顶点的邻接点共需要O(E)的时间,时间复杂度为O(|V|+|E|).
4.广度优先生成树
在广度优先遍历的过程中，将所有结点时经过的路径连上就是一颗生成树。
广度优先生成树由广度优先遍历过程确定。
由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树,也不唯一。
对非连通图的广度优先遍历，可得到广度优先生成森林。
