资源描述：
《最小生成树实验指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验1采用普里姆(prim)算法构造网络的最小生成树1、实验目的：深入理解最小生成树的概念，熟练掌握普里姆(prim)算法的工作过程，并通过定义合适的数据结构，釆用C语言程序实现。2、实验内容：根据模板程序编制普里姆算法的程序，在计算机中进行调试，同时寻找两个结点大于6的网络，利用文件读入其邻接矩阵，运行程序。记录运行结果，并把运行结果与手工生成的结果进行比较，验证程序的正解性。要求从文本文件中读入网络的邻接矩阵。3、实验原理①prim算法的主要步骤②数据表示③算法实现细节4、实验步骤与实验结果①编写"im算法的C语言程序
2、②输入计算机进行调试③准备两个顶点大于6的网络，把网络的邻接矩阵输入文本文件中，运行程序，记录程序的运行结果，根据结果画出最小生成树，并与手工生成的最小生成树进行比较。实验结果：①画出网络图，写出相应的邻接矩阵②记录程序的运行结果，根据结果画出最小生成树并写出最小生成树的权值。附录：程序模板#include/*定义一个结构体，用于记录一条边的始点与终点*/typedefstructpp{intp,q;}edge;intg[100][100],u[100],v[100],vexnum;edgep[100];
3、//用于记录最小生成树的各条边voidinput()//读入图的邻接矩阵{inti,j,temp;FILE*fp;fp=fopen("pp5.txt","r");fscanf(fp,"%d"，&vexnum);for(i=1;i<=vexnum;i++){printf(Hn);for(j=1;j<=vexnum;j++){fscanf(fp,"%d",&temp);g[i][jl=temp;printf(”％d",temp);}}fclose(fp);}main(){inti,j,k,m,n,ma,s=0;inputO
4、;//输入数据for(ih;iUvexnum;i++)//集合V中包含了所有顶点v[i]二1；u[1]=1；v[1]=0;//第1个节点加入至集合U中，并从集合V中去掉for(i=1;i<=vexnum-1;i++)//最多需vexnum-1条边{〃以下找连接节点集U至节点集V的最小边ma=1000;//ma存放最小边的权值for(j=1;j<=i;j++)//集合U中的第j个节点，其编号为u[j],每次增加一个，共for(k=1;k<=vexnum;k++)/*v[k]!=0表示节点k在集合V中;g[u[j][k]>0表
5、示有边*/if(v[k]!=0&&ma>g[u[j]][k]&&g[u[j]][k]>0){ma二g[u[j]][k]；//保存最小边值m二u[j];//最小边的始点编号n二k;//最小边的终点编号}s=s+ma;//求和u[i+1]=n;v[n]=0;//把找到最小边的终点编号从V中去掉，并加入至U中p[i].p二m;p[i].q二n;//保存最小边的始点编号与终点编号}printfC'H)；for(i=1;i<=vexnum-1;i++)printf("%d%d%d",p[i].p,p[i].q,g[p[i].
6、p][p[i].q]);printf("sum=%d",s);实验2采用克鲁斯卡尔(kruskal)M法构造网络的最小生成树1、实验目的：深入理解最小生成树的概念，熟练掌握克鲁斯卡尔(kruskal)算法的工作过程，并通过定义合适的数据结构，采用C语言程序实现。2、实验内容：根据模板程序编制克鲁斯卡你算法的程序，在计算机中进行调试，同时寻找两个结点大于6的网络，利用文件读入其邻接矩阵，运行程序。记录运行结果，并把运行结果与手工生成的结果进行比较，验证程序的正解性。要求从文本文件中读入网络的邻接矩阵。3、实验原理
7、①克鲁斯卡你算法的主要步骤②数据表示③算法实现细节4、实验步骤与实验结果①编写kruskal算法的C语言程序②输入计算机进行调试③准备两个顶点大于6的网络，把网络的邻接矩阵输入文本文件中，运行程序，记录程序的运行结果，根据结果画出最小生成树，并与手工生成的最小生成树进行比较。实验结果：①画出网络图，写出相应的邻接矩阵②记录程序的运行结果，根据结果画出最小生成树并写出最小生成树的权值。附录：程序模板#incIudetypedefstructpp//定义最小生成树连的结构{intp,q,r;//顶点1,顶点2
8、,权值}edge;intg[100][100],sort[100],vexnum;//定义图的邻接矩阵，集合，顶点数edgep[100],temp;voidinput()//读入图的邻接矩阵{inti,j,temp;FILE*fp;fp=fopen("pp5.txt","r");fseanf(fp,H%
