《数据结构实验三,prim最小生成树.doc》由会员分享，可在线阅读，更多相关《数据结构实验三,prim最小生成树.doc（5页珍藏版）》请在金锄头文库上搜索。
1、实验三：Prim最小生成树（验证性、4学时）一、 实验目的和要求理解图的遍历理解构造无向联通图的最小生成树的方法（Prim算法实现）能用Prim算法构造最小生成树出来二、 实验内容和原理 实验内容：用Prim算法构造一颗最小生成树(2) 实验原理： 从网中任一顶点开始，先把该顶点包含在生成树中，此时生成树只有一个顶点。找出一个端点在生成树中另一端点在生成树外的所有边，并把权值最小的边连到同它所关联的另一个顶点添加到生成树中；当有两条及以上具有相同最小权值的边可供选择时，任选一条。反复执行，直到所有顶点都包含在生成树时为止。三、 实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域
2、网环境软件：（1）Windows XP中文操作系统 （2）Turbo C 3.0四、 算法描述及实验步骤1、 描述从连通网中的某一定点开始，以此作为生成树的初始状态，然后不断地将网中的其他顶点添加到生成树上，知道最后一个顶点添加到生成树上是得到最小生成树。一个无向连通网的生成树可能不是唯一的，当总代价一定是最小的。2、算法流程图struct MGraph 定义图 输入顶点边数各顶点值记录所输各边树权值 不是最小值最小值将最小权值记在min中输出最小边及权值输出最小生成树各边3、代码(注释)#include #include #include #include #define MAX_NAME
3、5 #define MAX_VERTEX_NUM 20 /*权的上限值*/ typedef char VertexMAX_NAME;/*顶点名字串*/ typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/*邻接距阵*/ struct MGraph/*定义图*/ Vertex vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; ; typedef struct Vertex adjvex; /*当前点*/ int lowcost; /*代价*/ minsideMAX_VERTEX_NUM;
4、 int LocateVex(MGraph G,Vertex u)/定位 int i; for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0)return i; return -1; void CreateGraph(MGraph &G) int i,j,k,w; Vertex va,vb; printf(请输入无向网G的顶点数和边数(以空格为分隔)n); scanf(%d %d,&G.vexnum,&G.arcnum); printf(请输入%d个顶点的值(%d个字符):n,G.vexnum,MAX_NAME); for(i=0;iG.vexnum;+i)
5、/* 构造顶点集*/ scanf(%s,G.vexsi); for(i=0;iG.vexnum;+i) /*初始化邻接矩阵*/ for(j=0;jG.vexnum;+j) G.arcsij=0x7fffffff; printf(请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): n,G.arcnum); for(k=0;kG.arcnum;+k) scanf(%s%s%d%*c,va,vb,&w); i=LocateVex(G,va); j=LocateVex(G,vb); G.arcsij=G.arcsji=w; /*对称*/ int minimum(minside SZ,MGraph
6、 G) int i=0,j,k,min; while(!SZi.lowcost)i+; min=SZi.lowcost; /*将最小权值记在min中*/ k=i; /*把与边关联的生成树外的顶点序号记在k中*/ for(j=i+1;j0&minSZj.lowcost) min=SZj.lowcost; k=j; return k; void MiniSpanTree_PRIM(MGraph G,Vertex u) int i,j,k; minside closedge; k=LocateVex(G,u); for(j=0;jG.vexnum;+j) strcpy(closedgej.adjve
7、x,u); closedgej.lowcost=G.arcskj; closedgek.lowcost=0; /*将顶点vk加入生成树中*/ printf(最小代价生成树的各条边为:n); for(i=1;iG.vexnum;+i) k=minimum(closedge,G); printf(%s-%s)n,closedgek.adjvex,G.vexsk); /*输出最小边及权值*/ closedgek.lowcost=0; for(j=0;jG.vexnum;+j) if(G.arcskjclosedgej.lowcost) strcpy(closedgej.adjvex,G.vexsk)
8、; closedgej.lowcost=G.arcskj; /*修改权值域*/ int main() MGraph g; CreateGraph(g); MiniSpanTree_PRIM(g,g.vexs0); system(PAUSE); return 0; 五、 调试过程(1) 没有定位（2）没有定义最小生成树（3）j的如何取值，循环没有六、 实验结果（1）实验数据1 实验结果1 实验数据2 实验结果2七、 总结（1）理解用prim算法构造无向联通图的最小生成树的方法；（2）对于如何能够求得最小生成树加深了了解；（3）熟悉的prim算法的构造最小生成树的思路和方法；并且能够运用prim算法构造出最小生成树。附录：1 宁正元 王秀丽.算法与数据结构.北京：清华大学出版社。2 宁正元 王秀丽 林大辉.算法与数据结构习题精解和实验指导.北京：清华大学出版社。3数据结构与程序设计（C语言描述）Robert L.Kruse著 清华大学出版社4实用算法的分析与程序设计 吴文虎 王建德 著 电子工业出版社
