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

第1页共2页《数据结构与关系数据库（本科）》实验报告姓名班级学号实验日期课程名称数据结构与关系数据库（本科）指导教师成绩实验名称：深度优先遍历以邻接表存储的图实验目的1、掌握以邻接表存储的图的深度优先遍历算法；实验环境硬件环境：微机软件环境：WindowsXP，VC6.0三、实验内容、步骤及结果1、实验内容：基于图的深度优先遍历编写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。2、代码：#include<stdio.h>#include<stdlib.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];voidCreateTestALGraph(ALGraph*G){/*建立有向图的邻接表存储*/ inti,j; EdgeNode*s; G->n=8;G->e=9; for(i=0;i<G->n;i++)/*建立有n个顶点的顶点表*/ { G->adjlist[i].vertex='1'+i;//转换为字符型 G->adjlist[i].firstedge=NULL;/*顶点的边表头指针设为空*/ } { i=0,j=1; s=(EdgeNode*)malloc(sizeof(EdgeNode));/*生成新边表结点s*/ s->adjvex=j;/*邻接点序号为j*/ s->next=G->adjlist[i].firstedge;/*将新边表结点s插入到顶点Vi的边表头部*/ G->adjlist[i].firstedge=s; i=0,j=2; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新边表结点s s->adjvex=j;//*邻接点序号为j s->next=G->adjlist[i].firstedge;///*将新边表结点s插入到顶点Vi的边表头部 G->adjlist[i].firstedge=s; i=1,j=3; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新边表结点s s->adjvex=j;//*邻接点序号为j s->next=G->adjlist[i].firstedge;//*将新边表结点s插入到顶点Vi的边表头部 G->adjlist[i].firstedge=s; i=1,j=4; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新边表结点s s->adjvex=j;//*邻接点序号为j s->next=G->adjlist[i].firstedge;//*将新边表结点s插入到顶点Vi的边表头部 G->adjlist[i].firstedge=s; i=2,j=0; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新边表结点s s->adjvex=j;//*邻接点序号为j s->next=G->adjlist[i].firstedge;//*将新边表结点s插入到顶点Vi的边表头部 G->adjlist[i].firstedge=s; i=2,j=6; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新边表结点s s->adjvex=j;//*邻接点序号为j s->next=G->adjlist[i].firstedge;//*将新边表结点s插入到顶点Vi的边表头部 G->adjlist[i].firstedge=s; i=3,j=4; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新边表结点s s->adjvex=j;//*邻接点序号为j s->next=G->adjlist[i].firstedge;//*将新边表结点s插入到顶点Vi的边表头部 G->adjlist[i].firstedge=s; i=4,j=3; s=(EdgeNode*)malloc(sizeof(EdgeNode));//*生成新边表结点s s->adjvex=j;//*邻接点序号为j s->next=G->adjlist[i].firstedge;//*将新边表结点s插入到顶点Vi的边表头部 G->adjlist[i].firstedge=s; }///*CreateALGraph}voidDFSTraverseAL(ALGraph*G){/*深度优先遍历以邻接表存储的图G*/ inti; for(i=0;i<G->n;i++) visited[i]=false;/*标志向量初始化*/ for(i=0;i<G->n;i++) if(!visited[i])DFSAL(G,i);/*vi未访问过，从vi开始DFS搜索*/}/*DFSTraveseAL*///intlevel=1;//递归进行的层数intexist_path_DFS(ALGraph*G,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{EdgeNode*p;intk;if(i==j)return1;//i就是jelse{visited[i]=true;//for(p=G->adjlist[i].firstedge;p;p=p->next,level--) for(p=G->adjlist[i].firstedge;p;p=p->next){ //level++;k=p->adjvex;if(!visited[k]&&exist_path_DFS(G,k,j)) {printf("V%d",k+1); return1;//i下游的顶点到j有路径 } }//for return0;}//else//if(level==1)return0;}//exist_path_DFSvoidmain(){ ALGraph*G; G=(ALGraph*)malloc(sizeof(ALGraph));CreateTestALGraph(G); inti,j;printf("请输入i和j的值格式：i,j\n"); scanf("%d,%d",&i,&j); i=i-1; j=j-1; if(i==j) { printf("i不能等于j\n"); } else { if(exist_path_DFS(G,i,j)) { printf("该路径存在。\n"); }else { printf("该路径不存在。\n"); } } }3、测试数据与实验结果分析（可以用组合键Alt+PrintScreen截图）：上述例子中建立的有向图2121543543该有向图的邻接链表如下序号标号0V11V22V3