数据结构实验报告-图实验

1、图实验，邻接矩阵的实现1.实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现2.实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历3设计与编码MGraph.h#ifndefMGraph_H#defineMGraph_HconstintMaxSize=10;templateclassMGraphpublic:MGraph（DataTypea,intn,inte）;MGraph（）voidDFSTraverse（intv）;voidBFSTraverse（intv）;private:DataTypevertex

2、MaxSize;intarcMaxSizeMaxSize;intvertexNum,arcNum;#endifMGraph.cpp#includeusingnamespacestd;#includeMGraph.hexternintvisitedMaxSize;templateMGraph:MGraph（DataTypea,intn,inte）inti,j,k;vertexNum=n,arcNum=e;for(i=0;ivertexNum;i+)vertexi=ai;for(i=0;ivertexNum;i+)for(j=0;jvertexNum;j+)arcij=0;for(k=0;karc

3、Num;k+)coutij;arcij=1;arcji=1;templatevoidMGraph:DFSTraverse(intv)coutvertexv;visitedv=1;for(intj=0;jvertexNum;j+)if(arcvj=1&visitedj=0)DFSTraverse(j);templatevoidMGraph:BFSTraverse(intv)intQMaxSize;intfront=-1,rear=-1;coutvertexv;visitedv=1;Q+rear=v;while(front!=rear)v=Q+front;for(intj=0;jvertexNum

4、;j+)if(arcvj=1&visitedj=0)coutvertexj;visitedj=1;Q+rear=j;MGraph_main.cpp#includeusingnamespacestd;#includeMGraph.hexternintvisitedMaxSize;templateMGraph:MGraph(DataTypea,intn,inte)inti,j,k;vertexNum=n,arcNum=e;for(i=0;ivertexNum;i+)vertexi=ai;for(i=0;ivertexNum;i+)for(j=0;jvertexNum;j+)arcij=0;for(

5、k=0;karcNum;k+)coutij;arcij=1;arcji=1;templatevoidMGraph:DFSTraverse(intv)coutvertexv;visitedv=1;for(intj=0;jvertexNum;j+)if(arcvj=1&visitedj=0)DFSTraverse(j);templatevoidMGraph:BFSTraverse(intv)intQMaxSize;intfront=-1,rear=-1;coutvertexv;visitedv=1;Q+rear=v;while(front!=rear)v=Q+front;for(intj=0;jv

6、ertexNum;j+)if(arcvj=1&visitedj=0)coutvertexj;visitedj=1;Q+rear=j;4.运行与测试5.总结与心得通过该实验的代码编写与调试，熟悉了邻接矩阵在图结构中的应用，在调试过程中遇到很多的问题，在解决问题过程中也使我的写代码能力得到提升，邻接表的实现1.实验目的（1）掌握图的逻辑结构（2）掌握图的邻接表存储结构（3）验证图的邻接表存储及其遍历操作的实现2.实验内容（1）建立一个有向图的邻接表存储结构（2）对建立的有向图进行深度优先遍历（3）对建立的有向图进行广度优先遍历3.设计与编码ALGraph.h#ifndefALGraph_H#def

7、ineALGraph_HconstintMaxSize=10;structArcNodeintadjvex;ArcNode*next;templatestructVertexNodeDataTypevertex;ArcNode*firstedge;templateclassALGraphpublic:ALGraph（DataTypea,intn,inte）;ALGraph（）;voidDFSTraverse（intv）;voidBFSTraverse（intv）;private:VertexNodeadjlistMaxSize;intvertexNum,arcNum;#endifALGraph

8、.cpp#includeusingnamespacestd;#includeALGraph.hexternintvisitedMaxSize;templateALGraph:ALGraph(DataTypea,intn,inte)ArcNode*s;inti,j,k;vertexNum=n;arcNum=e;for(i=0;ivertexNum;i+)adjlisti.vertex=ai;adjlisti.firstedge=NULL;for(k=0;karcNum;k+)coutij;s=newArcNode;s-adjvex=j;s-next=adjlisti.firstedge;adjl

9、isti.firstedge=s;templateALGraph:ALGraph()ArcNode*p=NULL;for(inti=0;inext;deletep;p=adjlisti.firstedge;templatevoidALGraph:DFSTraverse(intv)ArcNode*p=NULL;intj;coutadjvex;if(visitedj=0)DFSTraverse(j);p=p-next;templatevoidALGraph:BFSTraverse(intv)intQMaxSize;intfront=-1,rear=-1;ArcNode*p=NULL;coutadj

10、vex;if(visitedj=0)coutnext;ALGraph_main.cpp#includeusingnamespacestd;#includeALGraph.cppintvisitedMaxSize=0;intmain()charch=A,B,C,D,E;inti;ALGraphALG(ch,5,6);for(i=0;iMaxSize;i+)visitedi=0;coutDepth-firsttraversesequenceis:;ALG.DFSTraverse(0);coutendl;for(i=0;iMaxSize;i+)visitedi=0;coutBreadth-firsttraversesequenceis:;ALG.BFSTraverse(0);coutendl;return0;4.运行与调试34vertices-uertices-uertices：vertices：vertices：twotyotyotyotyoEntzi-ofofofofofrauFibernunbsrnunbBFnunbsrnunbarcfofofofofthethethethetheProcessexitedwitJipetutnvalue凶Pressanykeytocontinue.setittlserialserialserialserialritasi