《用Prim算法构造最小生成树》由会员分享，可在线阅读，更多相关《用Prim算法构造最小生成树（8页珍藏版）》请在金锄头文库上搜索。
1、typedef struct int no;string name; VertexType;typedef struct int edgesMAXVMAXV;/*图的定义*/*邻接矩阵*/用Prim算法构造最小生成树班级：2010级计算机1班 学号：2010131116 姓名：杨才一、实验目的 了解最小生成树的概念，掌握生成最小生成树的方法。二、实验内容建立一个含任意结点的无向连通网，并用Prim算法构造其最小 生成树三、实验要点及说明 如果无向连通图是一个网，则其所有生成树中必有一棵树的边的权值 总和最小，这棵生成树为最小生成树。Prim算法：在图G二(V，E) (V为顶点集，E为边集)中任
2、选一 顶点v0,令集合U二v0为初态，在一个顶点在U中，另一顶点在V-U 中的所有边中找权值最小的边(u,v) (UE u,v V-U),并将v加入 到U中，同时将边(u,v)加入集合T中(T的初态为空集)，这样不 断地扩大U,直至U二V,则集合T中的边为所求最小生成树的边四、算法思想与算法描述1、邻接矩阵的数据类型的定义如下：/*顶点编号*/*顶点其他信息*/*顶点类型*/int vexnum,arcnum;/*顶点数,弧数*/VertexType vexsMAXV; /*存放顶点信息*/MGraph;2、临时数组的存放的数据类型struct int closes t; / U集中的顶点序号
3、 int lowcost; / 边的权值 closedgeMAXV;int const INF=32767; /*INF表示8*/3、prime算法实现：(原理见实验说明)void prime(MGraph g,int v)int lowcostMAXV;int min;int closestMAXV;int i,j,k;for(i=0;ig.vexnum;i+)lowcosti=g.edgesvi; closesti=v;for(i=1;ig.vexnum;i+)min=INF;for(j=0;jg.vexnum;j+) if(lowcostj!=0&lowcostjmin) min=low
4、costj; k=j;printf(边(%d,%d)权为:%dn,closestk,k,min); lowcostk=0;for(j=0;jg.vexnum;j+) if(g.edgeskj!=0&g.edgeskjn;M.vexnum=n;cou t输入弧数:； cine; M.arcnum=e;for(int i=0;in;i+)for(int j=0;jn;j+)if(i=j) M.edgesij=0;elseM.edgesij=INF;cout输入边的权：(如1 2 3表示点到点的权时)endl;for(int i=0;ixyz; M.edgesxy=z;cout输入点编号，名字：en
5、dl;for(int i=0;iNostr; M.vexsi.name=str; M.vexsi.no=No;int const MAXV=164、主函数int main(void)MGraph m;CreatMGraph(m);cout输出无向图的二维矩阵：endl;for(int i=0;im.vexnum;i+)for(int j=0;jm.vexnum;j+)if(m.edgesij=INF) cout ;else coutm.edgesij ; coutendl;cout输入最小生成树：endl;prime(m,0);return 0;五、实验测试及结果1.输入图的定点数和边数cai
6、| C:Wi n dowssysiem 3 2cnri2输入邻矩阵:1输入叢的权：（如12 3表示点1到点2的权时3）0 160 2 10 3 5II 0 611 2 511 4 6h 0 1h 1 5h 3 5h 4 6h 5 4h 0 5h 2 5h 5 2|4 2 6|4 5 3|4 1 3k 3 2k 2 4k 4 6_3顶点编号级名字的输入:输入点编号，名字:0 A1 B2 C3 D4 E5 F4. 运行结果:输岀无向图的二维矩阵:6042066430边为：4边X为汐边5为汚边X为汚 请按任意键靈续六、总结与体会实验任务基本完成，加深队算法思想的认识附源码：#include #inc
7、lude using namespace std; int const MAXV=16;typedef struct int no;string name; VertexType;/*图的定义*/*邻接矩阵*/*顶点编号*/*顶点其他信息*/*顶点类型*/typedef struct int edgesMAXVMAXV;int vexnum,arcnum; /*顶点数,弧数*/VertexType vexsMAXV; /*存放顶点信息*/MGraph;struct int closes t; / U集中的顶点序号 int lowcost; / 边的权值 closedgeMAXV;int con
8、st INF=32767; /*INF表示8*/ void prime(MGraph g,int v)int lowcostMAXV;int min;int closestMAXV;int i,j,k;for(i=0;ig.vexnum;i+)lowcosti=g.edgesvi; closesti=v;for(i=1;ig.vexnum;i+)min=INF;for(j=0;jg.vexnum;j+) if(lowcostj!=0&lowcostjmin) min=lowcostj;k=j;printf(边(%d,%d)权为:%dn,closestk,k,min); lowcostk=0;f
9、or(j=0;jg.vexnum;j+) if(g.edgeskj!=0&g.edgeskjn;M.vexnum=n;cou t输入弧数:； cine;M.arcnum=e;for(int i=0;in;i+)for(int j=0;jn;j+) if(i=j)M.edgesij=0;elseM.edgesij=INF;cout输入边的权：(如1 2 3表示点到点的权时)endl;for(int i=0;ixyz;M.edgesxy=z;cout输入点编号，名字：endl;for(int i=0;in;i+)int No;string str; cinNostr;M.vexsi.name=str;M.vexsi.no=No;int main(void)MGraph m;CreatMGraph(m);cout输出无向图的二维矩阵：endl;for(int i=0;im.vexnum;i+)for(int j=0;jm.vexnum;j+)if(m.edgesij=INF)cout ;elsecoutm.edgesij ;coutendl;cout输入最小生成树：endl;prime(m,0);return 0;
