用prim算法构造最小生成树

《用prim算法构造最小生成树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案用Prim算法构造最小生成树班级：2010级计算机1班学号：2010131116姓名：杨才一、实验目的了解最小生成树的概念，掌握生成最小生成树的方法。二、实验内容建立一个含任意结点的无向连通网，并用Prim算法构造其最小生成树三、实验要点及说明如果无向连通图是一个网，则其所有生成树中必有一棵树的边的权值总和最小，这棵生成树为最小生成树。Prim算法：在图G=（V，E）（V为顶点集，E为边集）中任选一顶点v0,令集合U={v0}为初态，在一个顶点在U中，另一顶点在V-U中的所有边中找权值最

2、小的边（u,v）（U∈u,v∈V-U），并将v加入到U中，同时将边（u,v）加入集合T中（T的初态为空集），这样不断地扩大U，直至U=V，则集合T中的边为所求最小生成树的边四、算法思想与算法描述1、邻接矩阵的数据类型的定义如下：typedefstruct{intno;/*顶点编号*/stringname;/*顶点其他信息*/}VertexType;/*顶点类型*/typedefstruct/*图的定义*/{intedges[MAXV][MAXV];/*邻接矩阵*/intvexnum,arcnum;/

3、*顶点数,弧数*/VertexTypevexs[MAXV];/*存放顶点信息*/}MGraph;2、临时数组的存放的数据类型struct{intclosest;//U集中的顶点序号intlowcost;//边的权值}closedge[MAXV];intconstINF=32767;/*INF表示∞*/3、prime算法实现：（原理见实验说明）voidprime(MGraphg,intv){intlowcost[MAXV];intmin;intclosest[MAXV];inti,j,k;for(i=

4、0;i

5、++)if(g.edges[k][j]!=0&&g.edges[k][j]>n;M.vexnum=n;cout<<"输入弧数:";cin>>e;M.arcnum=e;for(inti=0;i

6、s[i][j]=0;elseM.edges[i][j]=INF;}}cout<<"输入边的权：（如123表示点到点的权时）"<>x>>y>>z;M.edges[x][y]=z;}cout<<"输入点编号，名字："<>No>>str;M.vexs[i].name=str;M.vexs[i].no=No;}}in

7、tconstMAXV=164、主函数intmain(void){MGraphm;CreatMGraph(m);cout<<"输出无向图的二维矩阵："<

8、实验测试及结果1.输入图的定点数和边数精彩文档实用标准文案2.输入邻矩阵：3.顶点编号级名字的输入：4.运行结果：六、总结与体会实验任务基本完成，加深队算法思想的认识精彩文档实用标准文案附源码：#include#includeusingnamespacestd;intconstMAXV=16;typedefstruct{intno;/*顶点编号*/stringname;/*顶点其他信息*/}VertexType;/*顶点类型*/ty