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

《数据构造实验报告-图的遍历.docx》由会员分享，可在线阅读，更多相关《数据构造实验报告-图的遍历.docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、入；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;iarcsi

3、j=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);p

4、rintf(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(输入无向图的顶点数和边数:);s

5、canf(%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

6、.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)实验经过中，总体来讲还算顺畅，但在编写经过中，要养成良好的编程习惯，以免出错后浪费大量的时间在查错上。