数据构造实验报告-图的遍历.docx

数据构造实验报告-图的遍历数据构造实验报告实验：图的遍历一、实验目的：1、理解并把握图的逻辑构造和物理构造邻接矩阵、邻接表2、把握图的构造方法3、把握图的邻接矩阵、邻接表存储方式下基本操作的实现算法4、把握图的深度优先遍历和广度优先原理二、实验内容：1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图3、深度优先遍历第一步中构造的图G，输出得到的节点序列4、广度优先遍历第一部中构造的图G，输出得到的节点序列三、实验要求：1、无向图中的相关信息要从终端以正确的方式输入；2、详细的输入和输出格式不限；3、算法要具有较好的强健性，对错误操作要做适当处理；4、程序算法作简短的文字注释。四、程序实现及结果：1、邻接矩阵：#include#include#defineVERTEX_MAX30#defineMAXSIZE20typedefstructintarcsVERTEX_MAXVERTEX_MAX;intvexnum,arcnum;MGraph;voidcreat_MGraph1(MGraph*g)inti,j,k;intn,m;printf("请输入顶点数和边数:");scanf("%d%d",g->vexnum=n;g->arcnum=m;for(i=0;iarcsij=0;while(1)printf("请输入一条边的两个顶点：n");scanf("%d%d",if(i=-1|j=-1)break;elseif(i=j|i>=n|j>=n)printf("输入错误,请重新输入！n");elseg->arcsij=1;g->arcsji=1;voidprintMG(MGraph*g)inti,j;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)printf("%d",g->arcsij);printf("n");printf("n");main()inti,j;intfg;MGraph*g1;g1=(MGraph*)malloc(sizeof(MGraph);printf("1:创立无向图的邻接矩阵nn");creat_MGraph1(g1);printf("n此图的邻接矩阵为：n");printMG(g1);2、邻接链表:#include#include#defineMAX_SIZE10typedefstructnodeintvertex;structnode*next;node,adjlistMAX_SIZE;adjlistg;intvisitedMAX_SIZE+1;intqueMAX_SIZE+1;voidcreat()intn,e;inti;intstart,end;node*p,*q,*pp,*qq;printf("输入无向图的顶点数和边数:");scanf("%d%d",for(i=1;ivertex=end;p->next=NULL;q=&gstart;while(q->next)q=q->next;q->next=p;p1=(node*)malloc(sizeof(node);p1->vertex=start;p1->next=NULL;q1=while(qq->next)q1=q1->next;q1->next=p1;voidbfs(intvi)intfront,rear,v;node*p;front=0;rear=1;visitedvi=1;que0=vi;printf("%d",vi);while(front!=rear)v=quefront;p=gv.next;while(p)if(!visitedp->vertex)visitedp->vertex=1;printf("%d",p->vertex);querear+=p->vertex;p=p->next;front+;intmain()creat();bfs(1);printf("n");return0;五实验心得与体会：(1)通过这次实验，使我基本上把握了图的存储和遍历，让我弄清楚了怎样用邻接矩阵和邻接链表对图进行存储(2)深度优先遍历和广度优先遍历都有着各自的优点，通经过序逐步调试，能够渐渐的理解这两种遍历方法的内涵和巧妙之处。(3)实验经过中，总体来讲还算顺畅，但在编写经过中，要养成良好的编程习惯，以免出错后浪费大量的时间在查错上。