最小生成树和最短路径-数据结构实验.docx

实验报告六月182015姓名:陈斌学号:E11314079专业:【实验名称】最小生成树和最短路径【实验目的】掌握最小生成树以及最短路径的相关概念;掌握Prim算法和Kruskal算法;掌握Dijkstra算法【实验内容】采用普里姆算法求最小生成树编写一个算法,(a)所示的无向带权图G采用普里姆算法输出从顶点V1出发的最小生成树。图的存储结构自选。对于上图,采用克鲁斯卡尔算法输出该图的最小生成树。(提示:,得有序边集E;为所有顶点辅设一个数组Vset,标记各顶点所处的连通分量,初始时各不相同。(i,j),检查顶点i和j是否属于同一连通分量,如是,则重取下一条边;否则,该边即为生成树的一条边,输出该边,同时将所有与j处于同一连通分量的顶点的Vset值都修改为与i的相同。-1条边。) 源代码::#include<>#include<>#include<>//malloc()#include<>//INT,MAX#include<>//EOF,NULL#include<>//atoi()#include<>//eof()#include<>//floor(),ceil(),abs()#include<>//exit()#include<>//cout,cin//函数结果状态代码#RUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1//;typedefintBoolean;//:#include""typedefintVRType;typedefcharInfoType;#defineMAX_NAME3/*顶点字符串的最大长度+1*/#defineMAX_INFO20/*相关信息字符串的最大长度+1*/typedefcharVertexType[MAX_NAME];/*图的数组(邻接矩阵)存储表示*/#defineINFINITYINT_MAX/*用整型最大值代替∞*/#defineMAX_VERTEX_NUM20/*最大顶点个数*/typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/typedefstruct{ VRTypeadj;/*顶点关系类型。对无权图,用1(是)或0(否)表示相邻否;*/ /*对带权图,c则为权值类型*/ InfoType*info;/*该弧相关信息的指针(可无)*/}ell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/ AdjMatrixarcs;/*邻接矩阵*/ intvexnum,um;/*图的当前顶点数和弧数*/ GraphKindkind;/*图的种类标志*/}MGraph;intLocateVex(MGraphG,VertexTypeu){/*初始条件:图G存在,u和G中顶点有相同特征*//*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/inti;for(i=0;i<;++i)if(strcmp(u,[i])==0)returni;return-1;}StatusCreateAN(MGraph&G){/*采用数组(邻接矩阵)表示法,构造无向网G*/inti,j,k,w;VertexTypeva,vb;printf("请输入无向网G的顶点数边数(用逗号隔开):");scanf("%d,%d",&,&);printf("请输入%d个顶点的值(<%d个字符;用空格隔开):\n",,MAX_NAME);for(i=0;i<;++i)/*构造顶点向量*/scanf("%s",[i]);for(i=0;i<;++i)/*初始化邻接矩阵*/for(j=0;j<;++j){[i][j].adj=INFINITY;/*网*/}printf("请输入%d条边的顶点1顶点2权值(用空格隔开):\n",);for(