1、数据结构实验图的基本操作浙江大学城市学院实验报告课程名称 数据结构 实验项目名称 实验十三十四 图的基本操作 学生姓名 专业班级学号 实验成绩 指导老师(签名 ） 日期 206/9 一.实验目的和要求1、掌握图的主要存储结构。2、学会对几种常见的图的存储结构进行基本操作。二.实验内容1、图的邻接矩阵定义及实现:建立头文件test13_AjM.h，在该文件中定义图的邻接矩阵存储结构,并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件tt1.cpp(以下图为例）,编译并调试程序,直到正确运行。2、图的邻接表的定义及实现:建立头文件ts3_
2、AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件tst13.中调用这些函数进行验证（以下图为例)。、填写实验报告,实验报告文件取名为eprt13c。4、上传实验报告文件repor1.doc到BB。注： 下载56Grpharixcp(邻接矩阵)和p25ahdjoi.p(邻接表)源程序,读懂程序完成空缺部分代码。三. 函数的功能说明及算法思路 (包括每个函数的功能说明，及一些重要函数的算法实现思路）四实验结果与分析(包括运行结果截图、结果分析等）五. 心得体会程序比较难写，但是可以通过之前的一些程序来找到一些
3、规律(记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录-源程序】56:/p-25 图的存储结构以 数组邻接矩阵 表示, 构造图的算法。#include #inle lue #incle tpedf chrVerexType; /顶点的名称为字符cot nt MaxVerexum0; /图的最大顶点数const nMaxEgum00; /边数的最大值tpedf int WeightType; /权值的类型cont WegtTye axValue276； /权值的无穷大表示typedefrxypeVexlitMaxVetxNum； 顶点信息,定点名称tpeef We
4、gtTypeMatrixMaxexNumMaVertxNu； 邻接矩阵typef eumDG,DN,G,NGraphn; /有向图,有向网,无向图，无向网typedef stru Vest vxs; / 顶点数据元素 AdjMatrix rcs； / 二维数组作邻接矩阵nt exnm,arcn; / 图的当前顶点数和弧数 GaphKin kn; / 图的种类标志 MGraph;vo CeateGah(MGraph&, rpKd)/ 采用数组邻接矩阵表示法,构造图G/构造有向网G nt i,j,;char v， w;G.kind=kd; /图的种类prinf（输入要构造的图的顶点数和弧数：);
5、scaf(d,%d,&G.vexu,&G.rcnum);getchar（)；/过滤回车 print(依次输入图的顶点名称ABD.等等：); for (=; ivexnum; i+)scanf（，&G.exi);/构造顶点数据etcar()；/过滤回车 for （=；iG.venum;i+) /邻接矩阵初始化 fr (j0;j头顶点名,权值 输入数据：如-B,3 n); ese prntf(按照： 尾顶点名头顶点名输入数据:A-); for(k=0; kG.arnum; +） /构造邻接矩阵 if(d=DN|kd) can(%-%，,&,&w，&)； /输入弧的两个定点及该弧的权重 else s
6、caf(%c-%c，&v,&w）; gtchr(); o(i=;i.veum； i+) f（G.vexi=v)a;/查找出v在exs中的位置i if(i=Gvexnum) cervrex ERO！;xit(1); fo(=0;jG.vexnu； j+)i（Gvsjw) break;查找出在exs中的位置 i(=.xnum) cerr头顶点名，权值 输入数据:如-B,2a-,5a-c，b,，d，3输出邻接矩阵 | 5 | | 4 | | | | | 7 | | | 3 | |Prs any ey coue*/vod PrintMGra(Graph G) int i，j； stch(Gind） c
7、ase G: fo(i0； iG.venum; i+) r (j=0; jGvexnum； +） prit( 2 | ，arsij）； pintf（); bak; cse : o (=0； i.vexnum;i+） for(j0; jG.vexnum；j+) if(arcsj!=Maaue） print( %.d ,rcij); ese prntf( | ); prntf(n)； bea; case : f(=； iG.vexnu; i+) for (=0； G.vexum；j+） rn（ %2. | ,Grcsij)； pintf(n); brak； ae A: /*完成构造无向网* * 请
8、模仿编写无向网 or (i=; iG.vexu; +） or （j=0; Gvxu; j+) if(.acj!=axValue)rinf（ %2.d ,G.rsj); ls printf( | ）; prntf(n）; rek； /*完成函数*void countdig(MGa ) /请完成计算图的入度或初度 (G.d=|G.kind=N）/计算有向图或网的各个顶点的入度与出度inoutD,in； in i,j; for(i=0;iGvxnm;i+） outD=inD0; f(j=；jGxnu;j+) (G.acsj!0&.arcs!=axVlue) out+;fo（j0;jG.vexnum；
9、j+) if(.cji!=0&G.rcsi!MaxValue) inD+； prinf(%c:出度是%d,入度是d，Ges,outD,nD); es / 计算无向图或网的度 int ，;nt Du; for（i=;G.xnu;+） Du=0; for(j=0；j.vexnum;j) if(.csi!=0&G.aij!=MaxVaue) u+； prinf(%c的度是%n，G.vexs,Du); /*参照p25设计深度有限搜索*void DFSMatrix(MGrh G,it i,int ,lvsited） coutG.vei ； ii=tue;fr(in 0；jn；+) if(G.arcj！=
10、&G.arcs!=MaxVal& !itdj) DFSMrx(,j,n,iited);/*参照p28设计广度有限搜索*voidBFSarix(MGraph G，nt i， int n , boovsited) cost intMaSz=3; i qMaxSiz=0; int front=0,rer=0; cut.vexsi ;siedi=te; q+ra=i; whie(font!=rear) ot=(ront+1)%MaSize;in k=qront； fo(intj;jn;+) if(.acsi!=&G.arcsj！=MaxVlue!visited) coG.vesj; visitedj=
11、true; ear=(rear+1)%xSize; qrear; voimain() MGah; itk;rintf(请选择图的种类：0:有向图,1:有向网,:无向图,:无向网. 请选择：）; scnf(d，k); sitch（k) /DG,N，AG,ANase 0： rtf(构造有向图n); CrateGrph(G,DG); / 采用数组邻接矩阵表示法，构造有向图 break； case 1: prinf(构造有向网）; CreateGraph（G,DN); /采用数组邻接矩阵表示法，构造有向网AG break; case 2: pritf（构造无向图n); reteGraph（G,A);
12、/ 采用数组邻接矩阵表示法，构造无向图AG eak; case： rintf(构造无向网n); CrateGph(G,AN）; / 采用数组邻接矩阵表示法,构造无向网AG brak; PritMGrah(G); /打印图的邻接矩阵 boo*visite=ne ool.vexum; nt i； cou按图的邻接矩阵得到的深度优先遍历序列enl;fr(=0;G.em;+)iitedi=flse; DFSMai（G,0,G.xnum,visited);cout按图的邻接矩阵得到的广度优先遍历序列enl;for(i=;i.vexnum;i+) visitedilse； FSMatri（，0,.vxnu
13、m,visited)；cout度:-acdc-d-c*/ #udeiotream.h#inlude#include #inudetypedef charVrxye； /顶点的名称为字符on int MaxVerteNm =1; /图的最大顶点数cnst int Madgum =100; 边数的最大值yedef it Weigype; /权值的类型onst Weighype MaxVlue =2767;/权值的无穷大表示ypede VeexTy Vexlis MaVertexum;/顶点信息,定点名称 /邻接矩阵typedef enum DG,D,G，A Graphind；/有向图，有向网,无向
14、图，无向网struct Edgode /链表边结点,表示弧int adjvex； /存放与头结点顶点有关的另一个顶点在邻接表(数组）中的下标。 Egeode *ext;/指向链表下一个结点 WighType in; 权重值，或为该弧相关信息;typedf truc Voe /邻接表,表示顶点 VetexTyp data; / 顶点数据，顶点名称 EdeNode *istc； / 指向边结点链表第一个结点 Vode, AListaVertexm;tyedf stuct AdjList verces； in vexnum,acu; /图的当前顶点数和弧数 GrapKin ki; / 图的种类标志
15、AGraph;vod eateGraph(ALr&G）/构造有向图G Egeode *p; n i,j,;car v,w; G.kind=G; /图的种类 print(输入要构造的有向图的顶点数和弧数：)； scanf(%d,d,&Genum,&.arcn);gear();/过滤回车 print（依次输入图的顶点名称ABCD.等等:n)； fo (i=0;B n)；fo (=0; kGcnum; k+) snf(c-c,v,&)； getchar（)； for(i0;i.vxnum;i+) if(G.vrtii.dat=)break;/查找出v在vts中的位置i if（i=G.venum) c
16、rrerte RR!;eit(); (j=0；jG.vexnum; +） (Gvertiesdta=) brea;/查找出w在verices中的位置i f(j.exnum) cerrino =Mxale; /图的权值默认为无穷大 p-nextG.vetesifirtrc; /插入链表 G.vrticeifirsta=; /voidCreaterp_N(ALGraph G)/构造有向网G EdgeNode *p; nt ,j，; char，;Weightype q;G.in=DN; /图的种类 pritf(输入要构造的有向网的顶点数和弧数:n)；scaf（%，%d,&G.vexnu，&Garcn
17、um); getchar();过滤回车 rintf(依次输入图的顶点名称ABCD.等等:n); for (i=0; i.vexnum；i+） scan(%c,&.vertces.ata);/构造顶点数据 G.vertesi.firsarcNUL; /初始化指向链表指针 ethar(）;过滤回车 prif(按照: 尾顶点名头顶点名,权值 输入数据：如A-B,8 n);fo (k=0； kG.c; +) scanf(%cc,%d，&,&w,q）;gthar(）；(i;iG.vexnum; i+) if(G.rtics.data=v） ea;查找出v在ertices中的位置i (=G.vexnum）
18、cerrvertex ERROR!;xi(1）; fo(j0；G.exum; j+） if（G.icejta=w) break;查找出w在vertice中的位置i i(jG.vexnum) crex=j; /置入弧尾顶点号 pifo q; /图的权值默认为无穷大 p-nex=G.verticesiirarc;/插入链表 G.verticesi.firarc=; void CreateGrapAG(ALGraph &G)/构造无向图G Eeo*p; in i,j，k;chr v,w; G.kind=A; /图的种类 prntf(输入要构造的有向图的顶点数和弧数:n）;scf(d,%,&G.vexnu,&G.acnum);getchar()；/过滤回车 prinf（依次输入图的顶点名称ABCD.等等：n); for （i=0; iG.vxu; i+) scnf（%c,&G.vertsidata);/构造顶点数据 .vertiei.rsar=NULL; /初始化指向链表指针
