文章目录算法思想算法实现遍历序列的 可变性复杂度分析广度优先生成树 / 森林算法思想核心思想从起始顶点出发先访问其所有邻接点再访问邻接点的邻接点类似于树的层次遍历。队列Queue存放待访问的顶点保证先入队的顶点先入先出FIFO。辅助数组 visited[]标记顶点是否被访问过防止走回头路避免死循环。算法实现// 遍历所有顶点 初始都为 falseboolvisited[MAX_VERTEX_NUM];//访问标记数组//对图G进行广度优先遍历voidBFSTraverse(Graph G){for(inti0;iG.vexnum;i)visited[i]FALSE;//访问标记数组初始化InitQueue(Q);//初始化辅助队列Qfor(inti0;iG.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(wFirstNeighbor(G,v);w0;wNextNeighbor(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生成森林。广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方式不唯一因此基于邻接表的广度优先生成树也不唯一。