图的遍历（广度优先遍历 BFS）

算法思想

核心思想：从起始顶点出发，先访问其所有邻接点，再访问邻接点的邻接点（类似于树的层次遍历）。

• 队列（Queue）：存放待访问的顶点，保证先入队的顶点先入先出（FIFO）。
• 辅助数组 visited[]：标记顶点是否被访问过（防止走回头路，避免死循环）。

算法实现

// 遍历所有顶点 初始都为 falseboolvisited[MAX_VERTEX_NUM];//访问标记数组//对图G进行广度优先遍历voidBFSTraverse(Graph G){for(inti=0;i<G.vexnum;++i)visited[i]=FALSE;//访问标记数组初始化InitQueue(Q);//初始化辅助队列Qfor(inti=0;i<G.vexnum;++i)//从0号顶点开始遍历if(!visited[i])//对每个连通分量调用一次BFSBFS(G,i);//vi未访问过，从vi开始BFS}// if(!visited[i]) BFS(G, i);// 如果图是非连通的（比如两个孤立的三角形），从顶点0出发的BFS只能访问到第一个三角形。// 没有这个外循环，顶点5（第二个三角形）永远不会被访问，遍历会漏掉大量数据。//广度优先遍历voidBFS(Graph G,intv){//从顶点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函数 的次数 = 连通分量数

遍历序列的 可变性

同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一；

同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一；

按顶点编号递增或链表顺序依次访问邻接点（看题目要求）。

入队顺序 = 访问顺序。

复杂度分析

空间复杂度：主要来自辅助队列和visited数组，均为O(|V|)。

时间复杂度：主要是访问 顶点 和 边

广度优先生成树 / 森林

• BFS生成树：遍历过程中，每个顶点第一次被访问时经过的边（当前顶点指向邻接点）所构成。

  • 连通图，共n nn个顶点：BFS生成树边数 =n − 1 \boldsymbol{n-1}n−1。

• BFS生成森林：针对非连通图；多次执行BFS，每一个连通分量生成一棵BFS树，全部合称为BFS生成森林。

广度优先生成树由广度优先遍历过程确定。

由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一。