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

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

1、..实验报告June182021：斌学号：E11314079专业：13计算机科学与技术数据构造第八次实验学号E11314079专业计算机科学与技术斌实验日期2021.06.18教师签字成绩实验报告【实验名称】最小生成树和最短路径【实验目的】(1)掌握最小生成树以及最短路径的相关概念；..word.zl...(1)掌握Prim算法和Kruskal算法；(2)掌握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#include

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

4、R0#defineINFEASIBLE-1//OVERFLOW在math.h中已定义为3typedefintStatus;typedefintBoolean;//布尔类型main.cpp:#include"head.h"typedefintVRType;typedefcharInfoType;#defineMAX_NAME3/顶点字符串的最大长度+1/#defineMAX_INFO20/相关信息字符串的最大长度+1/typedefcharVertexType[MAX_NAME];/图的数组(邻接矩阵)存储表示/#defineINFINITYI

5、NT_MAX/用整型最大值代替∞/#defineMAX_VERTEX_NUM20/最大顶点个数/typedefenum{DG,DN,AG,AN}GraphKind;/{有向图,有向网,无向图,无向网}/..word.zl...typedefstruct{VRTypeadj;/顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；//对带权图，c那么为权值类型/InfoTypeinfo;/该弧相关信息的指针(可无)/}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct

6、{VertexTypevexs[MAX_VERTEX_NUM];/顶点向量/AdjMatrixarcs;/邻接矩阵/intvexnum,arum;/图的当前顶点数和弧数/GraphKindkind;/图的种类标志/}MGraph;intLocateVex(MGraphG,VertexTypeu){/初始条件:图G存在,u和G中顶点有一样特征//操作结果:假设G中存在顶点u,那么返回该顶点在图中位置;否那么返回-1/inti;for(i=0;i

7、ord.zl...return-1;}StatusCreateAN(MGraph&G){/采用数组(邻接矩阵)表示法,构造无向网G/inti,j,k,w;VertexTypeva,vb;printf("请输入无向网G的顶点数边数(用逗号隔开):");scanf("%d,%d",&G.vexnum,&G.arum);printf("请输入%d个顶点的值(<%d个字符;用空格隔开):",G.vexnum,MAX_NAME);for(i=0;i

8、;i