无向邻接图的深度优先遍历.doc

无向邻接图的深度优先遍历1(理解并实现无向图邻接表的创建的算法,理解并实现无向图的深度优先遍历的算法;转换成程序并上机实现,并按要求撰写实验报告;1(设计数据结构采用图的无向邻接表的存储结构,具体用C语言描述如下:typedefcharVertexType;typedefstructnode{/*边表结点*/intadjvex;/*邻接点域*/structnode*nextedge;/*链域*/}EdgeNode;typedefstructvnode{/*顶点表结点*/VertexTypevertex;/*顶点域*/EdgeNode*firstedge;/*边表头指针*/}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];/*AdjList时邻接表类型*/typedefstruct{AdjListadjlist;/*邻接表*/intn,e;/*图中当前顶点数和边数*/intkind;/*图的种类标志*/}AlGraph;2(根据实验内容的描述设计每个算法。最终程序代码:第一题/*无向图邻接表的深度优先遍历*/#include<>#include<>#defineMAX_VERTER_NUM20/*无向图的最大顶点数*/ode{/*边表结点*/intadjvex;/*邻接点域*/ode*nextarc;/*链域*/}ode;typedefstructVNode{/*顶点表结点*/intdata;/*顶点信息*/ode*firstarc;/*边表头指针,指向第一个依附该顶点的边的指针*/}VNode,AdjList[MAX_VERTER_NUM];typedefstruct{/*图*/AdjListvertices;intvexnum,um;/*图当前顶点数和边数*/}ALGraph;intvisited[MAX_VERTER_NUM];/*标记已被访问过的顶点(全局变量)*/intn=1;intLocateVex(ALGraph*G,intv)/*寻找节点V的位置*/{intk,n;for(k=0;k<G->vexnum;k++){if(G->vertices[k].data==v){n=k;break;}}returnn;}/*无向邻接表的深度优先遍历*/voidDFS(ALGraph*G,intv){ode*p;p=G->vertices[v].firstarc;if(n<G->vexnum){printf("V%d-->",G->vertices[v].data);n++;}else{printf("V%d\n",G->vertices[v].data);}visited[v]=1;while(p){if(!visited[p->adjvex])DFS(G,p->adjvex);p=p->nextarc;}}/*打印邻接表*/voidPrint_ALGraph(ALGraph*G){inti;ode*a3;printf("\n打印无向图邻接表:\n");for(i=0;i<G->vexnum;i++){printf("%dV%d|",i,G->vertices[i].data);if(G->vertices[i].firstarc!=NULL){a3=G->vertices[i].firstarc;while(a3){printf("-->%d",a3->adjvex);a3=a3->nextarc;}}printf("\n");}}/*插入邻接点的下标*/voidInsertadj(ALGraph*G,inti,intj){ode*a1,*a2;a1=(ode*)malloc(sizeof(ode));a1->adjvex=j;a1->nextarc=NULL;if(G->vertices[i].firstarc==NULL){G->vertices[i].firstarc=a1;}else{a2=G->vertices[i].firstarc;while(a2->nextarc){a2=a2->nextarc;}a2->nextarc=a1;}}/*初始化图并创建图*/voidInit_ALGraph(ALGraph*G){intv,v1,v2,i,j,q,p;printf("创建你的图:\n");printf("请输入图的点数和边数,中间用逗号隔开,结束请按回车\n");printf("输入(点,边):");scanf("%d,%d",&G->vexnum,&G->um);for(v=0;v<G->vexnum;v++){printf("输入点V%d:",(v+1));scanf("%d",&(G->vertices[v].data));