数据结构实验报告-图的遍历

《数据结构实验报告-图的遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验报告实验：图的遍历一、实验目的：1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表2、掌握图的构造方法3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法4、掌握图的深度优先遍历和广度优先原理二、实验内容：1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图3、深度优先遍历第一步中构造的图G，输出得到的节点序列4、广度优先遍历第一部中构造的图G，输出得到的节点序

2、列三、实验要求：1、无向图中的相关信息要从终端以正确的方式输入；2、具体的输入和输出格式不限；3、算法要具有较好的健壮性，对错误操作要做适当处理；4、程序算法作简短的文字注释。四、程序实现及结果：1、邻接矩阵：#include#include#defineVERTEX_MAX30#defineMAXSIZE20typedefstruct{intarcs[VERTEX_MAX][VERTEX_MAX];intvexnum,arcnum;}MGraph;voidcreat_MGr

3、aph1(MGraph*g){inti,j,k;intn,m;printf("请输入顶点数和边数:");scanf("%d%d",&n,&m);g->vexnum=n;g->arcnum=m;for(i=0;iarcs[i][j]=0;while(1){printf("请输入一条边的两个顶点：");scanf("%d%d",&i,&j);if(i==-1

4、

5、j==-1)break;elseif(i==j

6、

7、i>=n

8、

9、j>=n){printf("输入错误,请

10、重新输入！");}else{g->arcs[i][j]=1;g->arcs[j][i]=1;}}}voidprintMG(MGraph*g){inti,j;for(i=0;ivexnum;i++){for(j=0;jvexnum;j++)printf("%d",g->arcs[i][j]);printf("");}printf("");}main(){inti,j;intfg;MGraph*g1;g1=(MGraph*)malloc(sizeof(MGraph));printf("1:

11、创建无向图的邻接矩阵");creat_MGraph1(g1);printf("此图的邻接矩阵为：");printMG(g1);}2、邻接链表:#include#include#defineMAX_SIZE10typedefstructnode{intvertex;structnode*next;}node,adjlist[MAX_SIZE];adjlistg;intvisited[MAX_SIZE+1];intque[MAX_SIZE+1];voidcreat

12、(){intn,e;inti;intstart,end;node*p,*q,*pp,*qq;printf("输入无向图的顶点数和边数:");scanf("%d%d",&n,&e);for(i=1;i<=n;i++){visited[i]=0;g[i].vertex=i;g[i].next=NULL;}printf("依次输入边:");for(i=1;i<=e;i++){scanf("%d%d",&start,&end);p=(node*)malloc(sizeof(node));p->vertex=end;p

13、->next=NULL;q=&g[start];while(q->next)q=q->next;q->next=p;p1=(node*)malloc(sizeof(node));p1->vertex=start;p1->next=NULL;q1=&g[end];while(qq->next)q1=q1->next;q1->next=p1;}}voidbfs(intvi){intfront,rear,v;node*p;front=0;rear=1;visited[vi]=1;que[0]=vi;printf("%d

14、",vi);while(front!=rear){v=que[front];p=g[v].next;while(p){if(!visited[p->vertex]){visited[p->vertex]=1;printf("%d",p->vertex);que[rear++]=p->vertex;}p=p->next;}front++;}}intmain(){creat(