数据结构课程实验报告学号：: 实验日期：2016.1.7 实验名称： 图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示， 以及在此两 种常用存储方式下深度优先遍历（DFS 和广度优先遍历（BFS 操作的实现。

、实验内容与实验步骤 题目1:对以邻接矩阵为存储结构的图进行 DFS 和BFS 遍历问题描述：以邻接矩阵为图的存储结构，实现图的 DFS 和BFS 遍历。

基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列测试数据：如图所示0 10 0 01 0 0 0 1A 0 10 101 0 0 0 00 0 0 1 0题目2:对以邻接表为存储结构的图进行 DFS 和BFS 遍历问题描述：以邻接表为图的存储结构，实现图的 DFS 和BFS 遍历。

基本要求：建立一个图的邻接表存贮，输出顶点的一种 DFS 和BFS 序列 测试数据：如图所示在此贴上调试好的程序#i nclude<stdio.h>#i nclude<malloc.h>#i ncludevstri ng.h>V0 V1V2 V3 V41 A 0 14A3 A 0 A3A#define M 100typedef struct node{char vex[M][2];int edge[M ][ M ];int n ,e;}Graph;in t visited[M];Graph *Create_Graph(){ Graph *GA;int i,j,k,w;GA=(Graph*)malloc(sizeof(Graph));printf ("请输入矩阵的顶点数和边数(用逗号隔开):\n");sca nf("%d,%d", &GA-> n,&GA->e);printf ("请输入矩阵顶点信息：\n");for(i = 0;i<GA-> n;i++)scan f("%s",&(GA->vex[i][0]),&(GA->vex[i][1]));for (i = 0;i<GA-> n;i++)for (j = 0;j<GA-> n;j++) GA->edge[i][j] = 0;for (k = 0;k<GA->e;k++){ printf ("请输入第％4条边的顶点位置(i,j)和权值(用逗号隔开): ",k+1);sca nf ("%d,%d,%d"，&i,&j, &w);GA->edge[i][j] = w;}return(GA);}void dfs(Graph *GA, i nt v){ int i;prin tf("%c%c\n",GA->vex[v][0],GA->vex[v][1]);visited[v]=1;for(i=0; i<GA->n; i++)if (GA->edge[v][i]==1 && visited[i]==0) dfs(GA, i);}void traver(Graph *GA){ int i；for(i=0; i<GA->n; i++)visited[i]=0;for(i=0; i<GA-> n;i++)if(visited[i]==0) dfs(GA, i);}void bfs( Graph *GA, i nt v){ int j,k,fro nt=-1,rear=-1;int Q[M];prin tf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;rear=rear+1;Q[rear]=v;while (fron t!=rear){ fron t=fro nt+1;k=Q[fro nt];for (j=0; j<GA- >n; j++)if (GA->edge[k][j]==1 && visited[j]==0){ prin tf("%c%c\n",GA->vex[j][0],GA->vex[j][1]); visited[j]=1;rear=rear+1;Q[rear]=j;}}}void traver1(Graph *GA){ int i;for (i=0; i<GA-> n;i++)visited[i]=0;for (i=0; i<GA->n; i++)if (visited[i]==0)bfs(GA, i);typedef struct NODE{ int adjvex;struct NODE *n ext;}ENode;typedef struct NODE1{ char vex[2];ENode *first;} VexNode;typedef struct FS1{VexNode GL[M];int bia n,top;}FS;FS *CreateGL(){ FS *kk=(FS *)malloc(sizeof(FS));int i,j,k;ENode *s;printf("请输入顶点数和边数(用逗号隔开)：\n");sca nf("%d,%d",&kk->top, & kk->bia n);printf("请输入顶点信息：\n");for (i=0; i<kk->top; i++){ sca nf("%s",kk->GL[i].vex);kk->GL[i].first=NULL; }printf("请输入边的信息(i,j): \n");for (k=0;k<kk->bia n;k++){ sca nf("\n%d,%d",&i,&j);s =(ENode*)malloc(sizeof(ENode)); s->adjvex=j;s-> next=kk->GL[i].first;kk->GL[i].first =s;}return kk;void DFS(FS *kk, i nt v){ ENode *w; int i;prin tf("%s\n",kk->GL[v].vex); visited[v]=1;w=kk->GL[v].first ;while (w!=NULL){ i=w->adjvex;if (visited[i]==0)DFS(kk,i);w=w- >n ext;}}void TRAVER(FS *kk){ int i;for(i=0; i<kk->top;i++) visited[i]=0;for(i=0; i<kk->top; i++)if(visited[i]==0)DFS(kk, i);}void BFS(FS *kk, i nt v){ int Q[M], front=-1,rear=-1;ENode *w;int i, k;prin tf("%s\n",kk->GL[v].vex); visited[v]=1;rear=rear+1; Q[rear]=v; while (fron t!=rear){ fron t=fro nt+1; k=Q[fro nt]; w=kk->GL[k].first; while(w!=NULL) { i=w->adjvex;if( visited[i]==0){ visited[i]=1; printf("%s",kk->GL[i].vex); rear=rear+1;Q[rear]=i;}w=w- >n ext;}}}void TRAVER1(FS *kk){ int i;for(i=0; i<kk->top;i++) visited[i]=0;for(i=0; i <kk->top;i++)if(visited[i]==0)BFS(kk,i);}int mai n(){int i=0;Graph *p;FS *q;while(i=1){/*建立菜单*/char jz[30]={"1.创建邻接矩阵"};char jd[30]={"2.邻接矩阵DFS 遍历"};char jb[30]={"3.邻接矩阵BFS遍历"};char bg[30]={"4.创建邻接表"};char bd[30]={"5.邻接表DFS 遍历"};char bb[30]={"6.邻接表BFS遍历"};char tc[30]={"7.退出"};char mn[30]={"菜单"};int l=strle n(jd);int o=strle n(mn);int m,n;prin tf("\n");for(m=0;m<=(2*l-o)/2;m++)printf("");prin tf("%s",m n);for(m=0;m<=(2*l-o)/2;m++) printf("");prin tf("\n");for(m=0;m<=2*l;m++)*\n",jz,jd,jb,bg,bd,bb,tc); for(m=0;m<=2*l;m++)prin tf("*");prin tf("\n");/*选择功能*/printf("请输入所需功能序号：");sca nf("%d",&n); switch( n){case 1: p=Create_Graph();break;case 2: traver(p);break;case 3: traver1(p);break;case 4: q=CreateGL();break;case 5: TRAVER(q);break;case 6: TRAVER1(q);break;case 7: retur n 0; default:pri ntf("输入功能序号有误！ \n");}}return 0; prin tf("*"); *\n* %sprin tf("\n");prin tf("* %s *\n* %s *\n* %s *\n* *\n* %s *\n* %s%s90iTJK四、运行结果：在此把运行结果从屏幕上拷下来贴在此L.甸建邻按矩阵2.邻捞矩阵UF 克直厉 空却長拒陋氏遍历 匸D.建邹接夫 匚卸接衷茁2遍历□ XO E :\Cer necrrDXiIrtua ISyEtem\5 …esE V7 琴单V乗单 戌■:口：壮：（£* X K 相fc 宜 宅 gc X 童扫4c 址** # * We* 3C ： |C 电斗 ＞二輩 请输入所需功能序号，EVI莖单T •退岀淸输入肝需功盘序号;e 乩卸接夬ME 盘圧匚劭轄耒丽2凰⑷ +-4=4=水V1V4VJ VIV4 请输入边旳低唱（ij j' iki L r 01.42r 12r 3k ”i 3=*=+■++4= #+#4=^ 芈****4=*云■芈*+乂卅斗:芈世+立卡卄北* 育输入所需功耕号；4 请输入顶做和边數:用逗号隔开h5 7 淸输入顶点信旦，了•退出测试数据要注意现实中矩阵是从1开始，而数组里是从0开始。