数据结构试验七_prim算法

1、数据结构实验七姓名：朱彦荣学号：20132184专业：软件工程2实验题目：prim算法上级系统：VC+6.0日期：2014/11/27实验内容用prim算法实现最小生成树。二.输入与输出输入：采用文件形式输入图的节点数，弧的数目，用三元组的形式输入弧的两个节点以及权重。输由：通过输由链接生成树的节点的次序以及对应边的权重得到最小生成树。三.关键数据结构与算法描述关键数据结构：无向图的数据结构，closedg瞰组的数据结构。具体如下：/*/typedefstructnetwork(intn;/实际节点数intarcnum;弧的数目doublewMAXSIZEMAXSIZE;/权重Network;

2、/构建带有权重的网络图结构typedefstruct(doublelowcost;节点的最小权重域intvex;/节点的对应顶点位置CD_TP;/*/算法描述：Prim算法的原理为构建closedg儆组，每个节点有两个域，分别为对应于生成树的最小权重的节点域以及该节点和最小生成树对应的最小权重数lowcost通过n-1次遍历，每次遍历都要加入一个与已有节点相邻的最小顶点，然后更新剩余节点的与最小生成树对应的最小权重，以便进行下次遍历，经过n-1次遍历之后得到n-1个与初始顶点相关的节点，同时也就是得到了n-1条弧，构成n个节点的最小生成树。具体算法如下：/*/for(i=0;i<G.n;

3、i+)从k号顶点出发(closedgei.vex=k;closedgei.lowcost=G.wki;/定第k行，按行遍历cout<<"生成树按照从第"<<k+1<<"节点依次连接的节点为"<<endl;closedgek.lowcost=0;/使第k行的权重由无穷大变为0,加入生成树cout<<k+1;/输出k号顶点，因从0开始for(m=0;m<G.n-1;m+)/n-1趟循环(for(i=0;i<G.n;i+)if(closedgei.lowcost>0)break;fo

4、r(j=i+1;j<G.n;j+)if(closedgej.lowcost>0&&closedgej.lowcost<closedgei.lowcost)i=j;/找到生成树外的最小权重作为添加对象cout<<","<<i+1;/输出i号顶点，因从0开始closedgei.lowcost=0;/添力口进入生成树for(j=0;j<G.n;j+)if(closedgej.lowcost>0&&closedgej.lowcost>G.wij)(closedgej.lowcost=G.wi

5、j;/更新符合条件closedge的最小权重域closedgej.vex=i;同时更新对应的节点关联到目前最小权重关联点icout<<endl<<"该生成树有"<<G.n<<"个节点，"<<G.arcnum<<"条弧"<<endl;cout<<"生成树的"<<G.n-1<<"条边及其权重为："<<endl;for(i=0;i<G.n;i+)if(i!=k)/k

6、为起始节点，与自身相隔无穷大(cout<<"("<<i+1<<","<<closedgei.vex+1<<")"cout<<"-"<<G.wiclosedgei.vex<<endl;/与上面两点对应deleteclosedge;/*/四.理论与测试首先是书上的一个例子。具体的图如下，经过5次遍历即可得到最小生成树：vl最小生成树如下：vlv5测试：在文件中输入如下信息:文件时用梢式(。)查看(V帮助(H)61553564

7、62o1234354566661112233354从V1开始遍历运行程序得到:隹成树按照从第T节点依次连接的节点为136425镂星康鬲看6个节点，1®条弧生成树的5条边及其权重为：(2,3)-5(3.1)70，6)-2(5,2)7(6,3)-4Pressanykeytocontinue然后再构建一个无向图如下:最小生成树如下:在文件中输入如下:文件的毫辑旧格式S>(V)帮助(H)13759767523534451112223运行后输出如下:E:VC+6.0Win7VersionMyl生成树按照从第1节点依次连接的节点为152,3,4卷星品树有5个节点，7条弧生成树的4条边及其权

8、重为：(2,1)-3(3,1)-7(43)-6(5,1)7Pres$anykeytocontinue五.附录（源代码）#include"iostream"#include"stdio.h"#include"stdlib.h"usingnamespacestd;#defineinfinity1000000/定义为无穷大#defineMAXSIZE100节点最大数typedefstructnetworkintn;实际节点数intarcnum;弧的数目doublewMAXSIZEMAXSIZE;权重Network;/构建带有权重的网络图结构

9、typedefstructdoublelowcost;/节点的最小权重域intvex;节点的对应顶点位置CD_TP;初始化图voidInitGraph(Network&G)FILE*fp;inti,j;intn;intarcnum;doubleweight;if(fp=fopen("F:Network.txt","r")=NULL)printf("can'topenthetext!/n");exit(0);fscanf(fp,"%d%d",&n,&arcnum);G.n=n;G.ar

10、cnum=arcnum;for(i=0;i<G.n;i+)for(j=0;j<G.n;j+)G.wij=infinity;/初始化为无穷大while(fscanf(fp,"%d%d%lf",&i,&j,&weight)!=EOF)G.wi-1j-1=weight;/依次读入权重G.wj-1i-1=weight;/构建无向图fclose(fp);关闭文件voidprim(Network&G,intk)/从顶点vk出发CD_TP*closedge=newCD_TPG.n;初始化closedgeinti,j,m;for(i=0;i<

11、;G.n;i+)从k号顶点出发closedgei.vex=k;closedgei.lowcost=G.wki;/定第k行，按行遍历cout<<"生成树按照从第"<<k+1<<"节点依次连接的节点为"<<endl;closedgek.lowcost=0;/使第k行的权重由无穷大变为0,加入生成树cout<<k+1;/输出k号顶点，因从0开始for(m=0;m<G.n-1;m+)/n-1趟循环for(i=0;i<G.n;i+)if(closedgei.lowcost>0)break

12、;for(j=i+1;j<G.n;j+)if(closedgej.lowcost>0&&closedgej.lowcost<closedgei.lowcost)i=j;找到生成树外的最小权重作为添加对象cout<<","<<i+1;输出i号顶点，因从0开始closedgei.lowcost=0;/添力口进入生成树for(j=0;j<G.n;j+)if(closedgej.lowcost>0&&closedgej.lowcost>G.wij)closedgej.lowcost=G.wi

13、j;/更新符合条件closedge的最小权重域closedgej.vex=i;同时更新对应的节点关联到目前最小权重关联点icout<<endl<<"该生成树有"<<G.n<<"个节点，"<<G.arcnum<<"条弧"<<endl;cout<<"生成树的"<<G.n-1<<"条边及其权重为："<<endl;for(i=0;i<G.n;i+)if(i!=k)/k为起始节点，与自身相隔无穷大cout<<"("<<i+1<<",&