数据结构实验---图的储存与遍历学号：姓名：实验日期： 2016.1.7实验名称： 图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。
二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。
基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。
测试数据：如图所示题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。
基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。
测试数据：如图所示V0 V1 V2 V3 V4三、附录：在此贴上调试好的程序。
#include<stdio.h> #include<malloc.h> #include<string.h>V0 V1V4V3V2⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=0100000001010101000100010A 1 0 1 0 334#define M 100typedef struct node{char vex[M][2];int edge[M ][ M ];int n,e;}Graph;int visited[M];Graph *Create_Graph(){ Graph *GA;int i,j,k,w;GA=(Graph*)malloc(sizeof(Graph));printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n");scanf("%d,%d",&GA->n,&GA->e);printf ("请输入矩阵顶点信息：\n");for(i = 0;i<GA->n;i++)scanf("%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 ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：",k+1);scanf ("%d,%d,%d",&i,&j,&w);GA->edge[i][j] = w;}return(GA);}void dfs(Graph *GA, int v){ int i;printf("%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, int v){ int j,k,front=-1,rear=-1;int Q[M];printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;rear=rear+1;Q[rear]=v;while (front!=rear){ front=front+1;k=Q[front];for (j=0; j<GA->n; j++)if (GA->edge[k][j]==1 && visited[j]==0){ printf("%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 *next;}ENode;typedef struct NODE1{ char vex[2];ENode *first;} VexNode;typedef struct FS1{VexNode GL[M];int bian,top;}FS;FS *CreateGL( ){ FS *kk=(FS *)malloc(sizeof(FS));int i,j,k;ENode *s;printf("请输入顶点数和边数(用逗号隔开)：\n");scanf("%d,%d",&kk->top, &kk->bian);printf("请输入顶点信息：\n");for (i=0; i<kk->top; i++){ scanf("%s",kk->GL[i].vex);kk->GL[i].first=NULL; }printf("请输入边的信息(i,j)：\n");for (k=0;k<kk->bian;k++){ scanf("\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, int v){ ENode *w; int i;printf("%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->next;}}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, int v){ int Q[M], front=-1,rear=-1;ENode *w;int i, k;printf("%s\n",kk->GL[v].vex);visited[v]=1;rear=rear+1; Q[rear]=v;while (front!=rear){ front=front+1;k=Q[front];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->next;}}}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 main(){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=strlen(jd);int o=strlen(mn);int m,n;printf("\n");for(m=0;m<=(2*l-o)/2;m++)printf(" ");printf("%s",mn);for(m=0;m<=(2*l-o)/2;m++)printf(" ");printf("\n");for(m=0;m<=2*l;m++)printf("*");printf("\n");printf("* %s *\n* %s*\n* %s *\n* %s *\n* %s *\n* %s *\n* %s*\n",jz,jd,jb,bg,bd,bb,tc);for(m=0;m<=2*l;m++)printf("*");printf("\n");/*选择功能*/printf("请输入所需功能序号：");scanf("%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: return 0;default:printf("输入功能序号有误！\n");}}return 0;}四、运行结果：在此把运行结果从屏幕上拷下来贴在此五、心得体会：测试数据要注意现实中矩阵是从1开始，而数组里是从0开始。