|
广度优先遍历(BreadthFirstTraversal) 广度优先遍历的递归定义 设图G的初态是所有顶点均未访问过在G中任选一顶点v为源点则广度优先遍历可以定义为首先访问出发点v接着依次访问 v的所有邻接点w w …w t 然后再依次访问与w l w …w t 邻接的所有未曾访问过的顶点依此类推直至 图中所有和源点v有路径相通的顶点都已访问到为止此时从v开始的搜索过程结束 若G是连通图则遍历完成;否则在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程直至G中所有顶点均已被访 问为止 广度优先遍历类似于树的按层次遍历采用的搜索方法的特点是尽可能先对横向进行搜索故称其为广度优先搜索(Breadth FirstSearch)相应的遍历也就自然地称为广度优先遍历 广度优先搜索过程 在广度优先搜索过程中设x和y是两个相继要被访问的未访问过的顶点它们的邻接点分别记为x x …x s 和y y …y t 为确保先访问的顶点其邻接点亦先被访问在搜索过程中使用FIFO队列来保存已访问过的顶点当访问x和y时这两个顶点相继 入队此后当x和y相继出队时我们分别从x和y出发搜索其邻接点x x …x s 和y y …y t 对其中未访 者进行访问并将其人队这种方法是将每个已访问的顶点人队故保证了每个顶点至多只有一次人队 广度优先搜索算法 ()邻接表表示图的广度优先搜索算法 void BFS(ALGraph*Gint k) {// 以v k 为源点对用邻接表表示的图G进行广度优先搜索 int i; CirQueue Q; //须将队列定义中DataType改为int EdgeNode *p; InitQueue(&Q);//队列初始化 //访问源点v k printf(visit vertex%eG>adjlist[k]vertex); visited[k]=TRUE; EnQueue(&Qk);//v k 已访问将其人队(实际上是将其序号人队) while(!QueueEmpty(&Q)){//队非空则执行 i=DeQueue(&Q); //相当于v i 出队 p=G>adjlist[i]firstedge; //取v i 的边表头指针 while(p){//依次搜索v i 的邻接点v j (令p>adjvex=j) if(!visited[p>adivex]){ //若v j 未访问过 printf(visitvertex%cC>adjlistlp>adjvex]vertex); //访问v j visited[p>adjvex]=TRUE; EnQueue(&Qp>adjvex);//访问过的v j 人队 }//endif p=p>next;//找v i 的下一邻接点 }//endwhile }//endwhile }//end of BFS |
