2023年数据结构实验报告图的遍历.pdf
数 据 结 构 实 验 报 告实验:图的遍历一、实验目的：1、理解并掌握图的逻辑结构和物理结构一一邻接矩阵、邻接表2、掌握图的构造方法3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法4、掌握图的深度优先遍历和广度优先原理二、实验内容：1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G,并用邻接矩阵存储改图。2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G,并用邻接表存储该图3、深度优先遍历第一步中构造的图G输出得到的节点序列4、广度优先遍历第一部中构造的图G输出得到的节点序列三、实验规定：1、无向图中的相关信息要从终端以对的的方式输入；2、具体的输入和输出格式不限；3、算法要具有较好的健壮性,对错误操作要做适当解决；4、程序算法作简短的文字注释。四、程序实现及结果：1、邻接矩阵：#i n c 1 ude#i n c lude#defin e VERT E X _M AX 30#d efine MAXSIZE 20ty p ed e f st r u ct(in t ar c s V ERTEX _M Ax EV E R T E X_MAX；int vexnum,a rcnum;MGraph；void creat_MGrap h 1(MGra p h*g)int i,j,k;i n t n,m;prin t f(请输入顶点数和边数：)；scan f(%d%d,&n,&m);g-v e xnum=n;g a rc n um=m;f o r (i=0;i n;i+)for(j=O;j a rc s i j=0;whil e(l)(pr i n t f(请输入一条边的两个顶点:n );scan f(%d%d,&i,&j);if(i=-l I|j=-1)“brea k；e 1 s e if (i=j|i =n|Ij=n)6 printf(输入错误，请重新输入！n);6)el s e6(66 g-a r c si E j =1;g-a resvoi d printMG(MG r a p h*g)int i,j;for(i=0;iv e xn u m；i+)for(j=O;jVg v exnum;j+)p r intf(%d,g-arcsij);p ri n tf(n )；pr i nt f(n);)main()(int i,j;int f g;MGraph*gl；pr i ntf(1:创建无向图的邻接矩阵nn);cr e a t _MGra p h l(gl);pr i nt f(n此图的邻接矩阵为:n);printMG(gl);gl=(MGra p h*)m a 1 1 oc(s i z e of(MGraph);2、邻接链表：#in c lude#inclu d e#defineMAX_S I ZE 1 0typedef str u ct node i n t v e rte x;tart,&end)；s t ruct node*ne x t；n ode,adjlistMAX_SIZE;ad j lis t g；i n t vis i t edMAX_SIZE+l;in t que MAX_S IZE+1;void c r e a t()(i nt n,e;i n t i;int start,end;n o d e*p,*q,*p p,*qq;printf(输入 无 向 图的顶点数和边数:)；sc a nf(%d%d,&n,&e);f or(i=1;i=n;i+)(a vi s itedfi=0;gi.vertex=i；。gi.next=NULL;)pr i ntf(依次输入边：n”)；f o r (i=1;iver t ex 二 en d；p n e x t=NULL;q=&g s t ar t ;whi 1 e(q ne x t)o q=q-nex t;q-nex t=p;p 1 =(node*)m a 1 1 o c(s i zeo f(nod e)；pl-v e rt e x=st a rt;。pl-ne x t=N ULL;ql=&g endl；w h i 1 e(q q-n ext)o q 1 =ql-n e x t;ql-nex t=p 1;v o id b f s(in t vi)(i n t f r ont,r e ar,v；o n o d e*p;of r ont=0;rea r=1;v i s it e d vi=1;quefO=vi;pr i ntf(n%d”，v i)；6while(front!=rea r)8 V =q ue f r o n t ;8 P=g v.n e x t;。whi 1 e(p)0 gif(!vi s itedfpve r tex)0 v isitedfp-v e rtex=1;p rintf(n%d n,p-ver t ex);a 匕 quer e ar+二 pvertex;O 0 6 p=p-next；00)。f r o nt+；。in t main()(cr e at()；b fs(l);op rintf(n );r e t u rn 0；234输入无向囹的顶点数和边数：8表次输入钳：112.233436?16788882 3 4 5 6 7 8p ress any key to cont inue五.实验心得与体会：(1)通过这次实验，使我基本上掌握了图的存储和遍历，让我弄清楚了如何用邻接矩阵和邻接链表对图进行存储(2)深度优先遍历和广度优先遍历都有着各自的优点，通过程序逐步调试，可以慢慢的理解这两种遍历方法的内涵和巧妙之处。(3)实验过程中，总体来说还算顺畅，但在编写过程中，要养成良好的编程习惯，以免犯错后浪费大量的时间在查 错 上。
