图的存储方法与最小生成树

数据结构与算法实验报告实验名称：图的存储方法与最小生成树班级：10软工转本1班姓名：季佳宾学号：10130605类型：综合实验地点：鹤琴404日期：2012.11.22一、实验目的：1.理解图的特征，理解最小生成树的概念与相关算法2.用c语言设计好图的邻接矩阵表示和邻接表表示，并实现它们之间相互转换的操作3.掌握最小生成树算法：普里姆算法4.调试程序，编译运行并用数据测试程序5.熟悉c语言编程二、实验环境：1.PC机一台（带有VS6.0软件）三、实验内容和要求：1、用c语言设计好图的邻接矩阵表示和邻接表表示，并实现它们之间相互转换的操作2、用c语言实现最小生成树算法：普里姆算法3、调试程序，编译运行并用数据测试程序4、认识和熟悉图，掌握最小生成树算法：普里姆算法5、采用通过独立分析算法的方式来实现相关函数，并与实验教材的实现代码做比较四、实验步骤：（对实验步骤的说明应该能够保证根据该说明即可重复完整的实验内容，得到正确结果。）1、对图的两种表示方法与最小生成树算法做分析1）设计它们的结构体表示方法2）设计和实现相关算法函数2、在VS6.0环境下编译实现代码1）编辑源程序，达到调试编译运行的目的2）利用数据进行测试验证五、实验结果与分析（含程序、数据记录及分析和实验总结等）：1图的存储方法与最小生成树代码如下所示：#includestdio.h#includemalloc.h#defineINF32767typedefintInfoType;#defineMAXV100typedefstruct{intno;InfoTypeinfo;}VertexType;typedefstruct{intedges[MAXV][MAXV];intvexnum,arcnum;VertexTypevexs[MAXV];}MGraph;typedefstructANode{intadjvex;structANode*nextarc;InfoTypeinfo;}ArcNode;typedefintVertex;typedefstructVnode{Vertexdata;ArcNode*firstarc;}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intn,e;}ALGraph;voidMatToList(MGraphg,ALGraph*&G){inti,j,n=g.vexnum;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;in;i++)G-adjlist[i].firstarc=NULL;for(i=0;in;i++)for(j=n-1;j=0;j--)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-info=g.edges[i][j];p-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=p;}G-n=n;G-e=g.arcnum;}voidListToMat(ALGraph*G,MGraph&g){inti,j,n=G-n;ArcNode*p;for(i=0;in;i++)for(j=0;jn;j++)g.edges[i][j]=0;for(i=0;in;i++){p=G-adjlist[i].firstarc;while(p!=NULL){g.edges[i][p-adjvex]=p-info;p=p-nextarc;}}g.vexnum=n;g.arcnum=G-e;}voidDispMat(MGraphg){inti,j;for(i=0;ig.vexnum;i++){for(j=0;jg.vexnum;j++)if(g.edges[i][j]==INF)printf(%3s,~);elseprintf(%3d,g.edges[i][j]);printf(\n);}}voidDispAdj(ALGraph*G){inti;ArcNode*p;for(i=0;iG-n;i++){p=G-adjlist[i].firstarc;if(p!=NULL)printf(%3d:,i);while(p!=NULL){printf(%3d,p-adjvex);p=p-nextarc;}printf(\n);}}voidmain(){inti,j;MGraphg,g1;ALGraph*G;intA[MAXV][6]={{0,5,0,7,0,0},{0,0,4,0,0,0},{8,0,0,0,0,9},{0,0,5,0,0,6},{0,0,0,5,0,0},{3,0,0,0,1,0}};g.vexnum=6;g.arcnum=10;for(i=0;ig.vexnum;i++)for(j=0;jg.vexnum;j++)g.edges[i][j]=A[i][j];printf(\n);printf(有向图G的邻接矩阵：\n);DispMat(g);G=(ALGraph*)malloc(sizeof(ALGraph));printf(有向图G的邻接矩阵转换成邻接表：\n);MatToList(g,G);DispAdj(G);printf(有向图G的邻接表换成邻接阵：\n);ListToMat(G,g1);DispMat(g1);printf(\n);}2算法结果如下所示:六：思考题：学生用户名密码liweiguostuliweiguostu