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

《最小生成树和最短路径 数据结构实验》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告六月182015姓名：陈斌学号：E11314079专业：13计算机科学与技术数据结构第八次实验学号E11314079专业计算机科学与技术姓名陈斌实验日期2015.06.18教师签字成绩实验报告【实验名称】最小生成树和最短路径【实验目的】(1)掌握最小生成树以及最短路径的相关概念；(2)掌握Prim算法和Kruskal算法；(3)掌握Dijkstra算法【实验内容】l采用普里姆算法求最小生成树(1)编写一个算法，对于教材图7.16(a)所示的无向带权图G采用普里姆算法输出从顶点V1出发的最小生成树。

2、图的存储结构自选。(2)对于上图，采用克鲁斯卡尔算法输出该图的最小生成树。（提示：a.先对边按权值从小到大排序，得有序边集E；为所有顶点辅设一个数组Vset，标记各顶点所处的连通分量，初始时各不相同。b.依次从E中取出一条边(i,j)，检查顶点i和j是否属于同一连通分量，如是，则重取下一条边；否则，该边即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的Vset值都修改为与i的相同。c.重复b步直至输出n-1条边。）源代码：head.h:#include#include

3、#include//malloc()#include//INT,MAX#include//EOF,NULL#include//atoi()#include//eof()#include//floor(),ceil(),abs()#include//exit()#include//cout,cin//函数结果状态代码#defineTRUE1

4、#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1//OVERFLOW在math.h中已定义为3typedefintStatus;typedefintBoolean;//布尔类型main.cpp:#include"head.h"typedefintVRType;typedefcharInfoType;#defineMAX_NAME3/*顶点字符串的最大长度+1*/#defineMAX_INFO20/*相关信息字符串的最大长度+1*/typedef

5、charVertexType[MAX_NAME];/*图的数组(邻接矩阵)存储表示*/#defineINFINITYINT_MAX/*用整型最大值代替∞*/#defineMAX_VERTEX_NUM20/*最大顶点个数*/typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/typedefstruct{VRTypeadj;/*顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；*//*对带权图，c则为权值类型*/InfoType*info;/*该

6、弧相关信息的指针(可无)*/}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图的当前顶点数和弧数*/GraphKindkind;/*图的种类标志*/}MGraph;intLocateVex(MGraphG,VertexTypeu){/*初始条件:图G存在,u和G中顶点

7、有相同特征*//*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/inti;for(i=0;i

8、m);printf("请输入%d个顶点的值(<%d个字符;用空格隔开):",G.vexnum,MAX_NAME);for(i=0;i