教黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 void DFS(Graph G,int v,Status (*Visit )(Graph G,int v)) { visited[v]=TRUE;Visit(G,v); for w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w)) if(!visited[w])DFS(G,w,Visit); } 3、基于某种存储结构的DFS算法 根据选择的存储结构，决定FirstAdjVex()和NextAdjVex()的实现，重新整合算法。 如采用邻接矩阵表示法表示的图，则DFS算法如下： void DFS(MGraph G,int v,Status(*Visit )(MGraph G,int v)) visited[v]=TRUE;Visit(G,v); for w=0;w<G.vexnum;w++) if(G.ares[vl[wl.adj &&!visited[w])DFS(G,w,Visit ) } 如采用邻接表表示法表示的图，则DFS算法如下： void DFS(ALGraph G,int v,Status(*Visit )(ALGraph G,int v)) { visited[v]=TRUE;Visit(G,v); for(p=G.vertices[v].firstarc;p;p=p->nextarc) if(!visited[p->adjvex])DFS(G,p->adjvex,Visit); 7.3.2广度优先搜索 1、分析 ·类似于树的层次遍历 ·引入visited访问标志数组 ·非连通图，需引入多个广度优先搜索的起始顶点 ·引入队列保存“顶点已访问，但其邻接点未全访问”的顶点编号 2、基于ADT Graph的BFS算法 void BFSTraverse(Graph G,Status(*Visit)(Graph 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=FirstAdiVex(G.u):w:w=NextAdiVex(G.u.w)) if(Ivisited[w]) 体访问顶点u的尚未访问的邻接点并入队*/ visited[w]=TRUE;Visit(G,w); EnQueue(Q,w); 文档编号 完成时间 完成人张昱 修改时间20026-6 第6页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 6 页 void DFS(Graph G, int v, Status ( *Visit ) (Graph G, int v) ) { visited[v] = TRUE; Visit(G, v); for ( w = FirstAdjVex(G, v); w; w = NextAdjVex(G, v, w) ) if ( !visited[w] ) DFS(G, w, Visit); } 3、基于某种存储结构的 DFS 算法 根据选择的存储结构，决定 FirstAdjVex()和 NextAdjVex()的实现，重新整合算法。 如采用邻接矩阵表示法表示的图，则 DFS 算法如下： void DFS (MGraph G, int v, Status ( *Visit ) (MGraph G, int v)) { visited[v] = TRUE; Visit(G, v); for ( w = 0; w < G.vexnum; w ++) if ( G.arcs[v][w].adj && !visited[w] ) DFS(G, w, Visit ); } 如采用邻接表表示法表示的图，则 DFS 算法如下： void DFS (ALGraph G, int v, Status ( *Visit ) (ALGraph G, int v) ) { visited[v] = TRUE; Visit(G, v); for ( p = G.vertices[v].firstarc; p ; p = p->nextarc) if (!visited[p->adjvex] ) DFS(G, p->adjvex, Visit); } 7.3.2 广度优先搜索 1、分析 ·类似于树的层次遍历 ·引入 visited 访问标志数组 ·非连通图，需引入多个广度优先搜索的起始顶点 ·引入队列保存“顶点已访问，但其邻接点未全访问”的顶点编号 2、基于 ADT Graph 的 BFS 算法 void BFSTraverse (Graph G, Status ( *Visit ) (Graph 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 = FirstAdjVex( G, u) ; w ; w = NextAdjVex(G, u, w) ) if ( !visited[w] ){ /* 访问顶点 u 的尚未访问的邻接点并入队 */ visited[w] = TRUE; Visit(G, w); EnQueue(Q, w); }