分别以邻接矩阵和邻接表作为图的存储结构.doc

《分别以邻接矩阵和邻接表作为图的存储结构.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分别以邻接矩阵和邻接表作为图的存储结构，给出连通图的深度优先遍历的递归算法算法思想：（1）访问出发点vi，并将其标记为已访问过。（2）遍历vi的的每一个邻接点vj，若vi未曾访问过，则以vi为新的出发点继续进行深度优先遍历。算法实现：Booleanvisited[max];//访问标志数voidDFS(GraphG,intv){//算法7.5从第v个顶点出发递归地深度优先遍历图Gintw;visited[v]=TRUE;printf("%d",v);//访问第v个顶点for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(

2、G,v,w))if(!visited[w])//对v的尚未访问的邻接顶点w递归调用DFSDFS(G,w);}/*****************************************************//*以邻接矩阵作为存储结构*/DFS1(MGraphG,inti){intj;visited[i]=1;printf("%c",G.vexs[i]);for(j=1;j<=G.vexnum;j++)if(!visited[j]&&G.arcs[i][j]==1)DFS1(G,j);}/*以邻接表作为存储结构*/DFS2(ALGraph

3、G,inti){intj;ArcPtrp;visited[i]=1;printf("%c",G.vertices[i].data);for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc){j=p->adjvex;if(!visited[j])DFS2(j);}}