敦案 第七章图 程序设计—数据结构 图的遍历算法及其应用 } 3、基于某种存储结构的BFS算法 如采用邻接矩阵表示法表示的网，则算法如下： void BFSTraverse(MGraph G,Status(*Visit )(MGraph G,int v)) for (v=0;v<G.vexnum;++v)visited[v]=FALSE; InitQueue(Q); for (v=0;v<G.vexnum;++v if(Ivisited[v]){ 体访问某连通分量的起始顶点，起点入队*/ visited[v]=TRUE;Visit(G,v); EnQueue(Q,v); while(!QueueEmpty(Q)){ *出队，访问出队元素的邻接点*/ DeQueue(Q,u); for w=0 w<G.vexnum;w++) if G.areslullw].adj!=INFINITY &&!visited[w]){ 体访问顶点u的尚未访问的邻接点并入队*/ visited[w]=TRUE;Visit(G,w); EnQueue(Q,w); 如采用邻接表表示法表示的网，则算法如下： void BFSTraverse(ALGraph G,Status (*Visit )(ALGraph G,int v)) for(v=0;v<G.vexnum;++v visited[v]=FALSE; InitQueue(Q); for v=0;v<G.vexnum;++v) if (!visited[v] 体访问某连通分量的起始顶点，起点入队/ visited[v]=TRUE;Visit(G,v); EnQueue(Q,v); while(!QueueEmpty(Q)){ 体出队，访问出队元素的邻接点*/ DeQueue(Q,u); for(p=G.vertices[ul.firstarc p;p=p->nextarc) if (!visited[p->adjvex]){ 体访问顶点u的尚未访问的邻接点并入队*/ visited[p->adjvex]=TRUE;Visit(G,p->adjvex); EnQueue(Q,p->adjvex); 文档编号 完成时间 完成人张昱 修改时间20026-6 第7页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 7 页 } } } 3、基于某种存储结构的 BFS 算法 如采用邻接矩阵表示法表示的网，则算法如下： void BFSTraverse(MGraph G, Status ( *Visit ) (MGraph G, int v) ) { for ( v = 0; v < G.vexnum; ++v ) visited[v] = FALSE; InitQueue(Q); for ( v = 0; v < G.vexnum; ++v ) if ( !visited[v] ){ /* 访问某连通分量的起始顶点，起点入队 */ visited[v] = TRUE; Visit(G, v); EnQueue(Q, v); while( !QueueEmpty(Q) ){ /* 出队，访问出队元素的邻接点 */ DeQueue(Q,u); for ( w = 0 ; w < G.vexnum; w++ ) if ( G.arcs[u][w].adj != INFINITY && !visited[w] ){ /* 访问顶点 u 的尚未访问的邻接点并入队 */ visited[w] = TRUE; Visit(G, w); EnQueue(Q, w); } } } } 如采用邻接表表示法表示的网，则算法如下： void BFSTraverse(ALGraph G, Status ( *Visit ) (ALGraph G, int v)) { for ( v = 0; v < G.vexnum; ++v ) visited[v] = FALSE; InitQueue(Q); for ( v = 0; v < G.vexnum; ++v ) if ( !visited[v] ){ /* 访问某连通分量的起始顶点，起点入队 */ visited[v] = TRUE; Visit(G, v); EnQueue(Q, v); while( !QueueEmpty(Q) ){ /* 出队，访问出队元素的邻接点 */ DeQueue(Q,u); for ( p = G.vertices[u].firstarc ; p ; p = p->nextarc ) if ( !visited[p->adjvex] ){ /* 访问顶点 u 的尚未访问的邻接点并入队 */ visited[p->adjvex] = TRUE; Visit(G, p->adjvex); EnQueue(Q, p->adjvex); } } } }