|
()邻接矩阵表示的图的广度优先搜索算法 void BFSM(MGraph *Gint k) {以v k 为源点对用邻接矩阵表示的图G进行广度优先搜索 int ij; CirQueue Q; InitQueue(&Q); printf(visit vertex%cG>vexs[k]); //访问源点v k visited[k]=TRUE; EnQueue(&Qk); while(!QueueEmpty(&Q)){ i=DeQueue(&Q); //v i 出队 for(j=;jn;j++)//依次搜索v i 的邻接点v j if(G>edges[i][j]==&&!visited[j]){//v i 未访问 printf(visit vertex%cG>vexs[j]);//访问v i visited[j]=TRUE; EnQueue(&Qj);//访问过的v i 人队 } }//endwhile }//BFSM () 广度优先遍历算法 类似于DFSTraverse【参见DFSTraverse算法】 图的广度优先遍历序列 广度优先遍历图所得的顶点序列定义为图的广度优先遍历序列简称BFS序列 ()一个图的BFS序列不是惟一的 ()给定了源点及图的存储结构时算法BFS和BFSM所给出BFS序列就是惟一的 【例】下图中G 以邻接矩阵为存储结构以v 为出发点的BFS搜索过程【 参见动画演示 】和BFS序列为V V V V V V V V 【例】上图中G 以邻接表为存储结构以v 为出发点的BFS搜索过程和BFS序列【 参见动画演示 】 算法分析 对于具有n个顶点和e条边的无向图或有向图每个顶点均入队一次广度优先遍历(BFSTraverse)图的时间复杂度和 DFSTraverse算法相同 当图是连通图时BFSTraverse算法只需调用一次BFS或BFSM即可完成遍历操作此时BFS和BFSM的时间复杂度分别为O(n+e)和 (n ) |
