2-深度优先遍历以邻接表存储的图-实验报告

第1页共3页福建江夏学院《数据结构与关系数据库（本科）》实验报告姓名班级学号实验日期课程名称数据结构与关系数据库（本科）指导教师成绩实验名称：深度优先遍历以邻接表存储的图一、实验目的1、掌握以邻接表存储的图的深度优先遍历算法；二、实验环境1、硬件环境：微机2、软件环境：WindowsXP，VC6.0三、实验内容、步骤及结果1、实验内容：基于图的深度优先遍历编写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。2、代码：#includestdio.h#includestdlib.h#defineMaxVertexNum100/*最大顶点数为100*/typedefcharVertexType;typedefstructnode{/*边表结点*/intadjvex;/*邻接点域*/structnode*next;/*指向下一个邻接点的指针域*//*若要表示边上信息，则应增加一个数据域info*/}EdgeNode;typedefstructvnode{/*顶点表结点*/VertexTypevertex;/*顶点域*/EdgeNode*firstedge;/*边表头指针*/}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];/*AdjList是邻接表类型*/typedefstruct{AdjListadjlist;/*邻接表*/intn,e;/*顶点数和边数*/}ALGraph;/*ALGraph是以邻接表方式存储的图类型*/boolvisited[MaxVertexNum];voidCreateALGraph(ALGraph*G)第2页共3页{/*建立有向图的邻接表存储*/inti,j,k;EdgeNode*s;printf(请输入顶点数和边数(输入格式为:顶点数,边数)：\n);scanf(%d,%d,&(G-n),&(G-e));/*读入顶点数和边数*/printf(请输入顶点信息(输入格式为:顶点号CR)：\n);for(i=0;iG-n;i++)/*建立有n个顶点的顶点表*/{scanf(\n%c,&(G-adjlist[i].vertex));/*读入顶点信息*/G-adjlist[i].firstedge=NULL;/*顶点的边表头指针设为空*/}printf(请输入边的信息(输入格式为:i,j)：\n);for(k=0;kG-e;k++)/*建立边表*/{scanf(\n%d,%d,&i,&j);/*读入边Vi,Vj的顶点对应序号*/s=(EdgeNode*)malloc(sizeof(EdgeNode));/*生成新边表结点s*/s-adjvex=j;/*邻接点序号为j*/s-next=G-adjlist[i].firstedge;/*将新边表结点s插入到顶点Vi的边表头部*/G-adjlist[i].firstedge=s;}}/*CreateALGraph*/voidDFSAL(ALGraph*G,inti){/*以Vi为出发点对邻接表存储的图G进行DFS搜索*/EdgeNode*p;printf(visitvertex:V%c\n,G-adjlist[i].vertex);/*访问顶点Vi*/visited[i]=true;/*标记Vi已访问*/p=G-adjlist[i].firstedge;/*取Vi边表的头指针*/while(p)/*依次搜索Vi的邻接点Vj，j=p-adjva*/{if(!visited[p-adjvex])/*若Vj尚未访问，则以Vj为出发点向纵深搜索*/DFSAL(G,p-adjvex);p=p-next;/*找Vi的下一个邻接点*/}}/*DFSAL*/voidDFSTraverseAL(ALGraph*G){/*深度优先遍历以邻接表存储的图G*/inti;for(i=0;iG-n;i++)visited[i]=false;/*标志向量初始化*/for(i=0;iG-n;i++)if(!visited[i])DFSAL(G,i);/*vi未访问过，从vi开始DFS搜索*/}/*DFSTraveseAL*/第3页共3页voidmain(){ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));CreateALGraph(G);printf(深度优先搜索结果：\n);DFSTraverseAL(G);}3、测试数据与实验结果分析（可以用组合键Alt+PrintScreen截图）：四、心得体会