《实习三--求无向连通图的生成树》由会员分享，可在线阅读，更多相关《实习三--求无向连通图的生成树（7页珍藏版）》请在金锄头文库上搜索。
1、 实习三 求无向连通图的生成树 1. 需求分析 问题描述： 若要在n个都市之间建设通信网络，只需要架设n-1条路线即可。如何 以最低的经济代价建设这个通信网，是一种网的最小生成树问题。 基本规定： (1)运用克鲁斯卡尔算法求网的最小生成树,其中,以课本8.7节中的等 价类表达构造生成树过程中的连通分量。 (2)运用普里姆算法求网的最小生成树。 (3)以文本文献形式输出生成树中各条边以及她们的权值。2. 设计（1）设计思想:创立邻接矩阵存储构造。本程序重要分为两个模块：创立邻接矩阵模块,最小生成树模块。创立邻接矩阵模块:以邻接矩阵的存储形式创立无向网。最小生成树模块：生成最小生成树，输出其各条边
2、及权值。（2）概要设计:it型 LoaeVe函数判断权值在矩阵的位置；声明Craeterp函数创立邻接矩阵；声明kruskal函数用于生成最小生成树;声明main函数为程序调用环节。（3)设计具体：a.将程序分为两个模块: B.主函数流程图: c.最小生成树流程图 (4）调试分析:-变量没定义就使用 解决:定义完变量在使用。 -子函数嵌套定义; 解决：子函数单独定义，可调用。 -使用数组是越界; 解决:注意数组的值，注意不能越界。(5) 顾客手册:.主页面： b.输入顶点数及边数的信息： .输入顶点信息: 输入顶点及权值： （6）测试成果：输出最小生成树及权值: (7)源程序：ind#nclu
3、deinldesring.h#efie MAX100#defneMAXVERTXNUM 2ted ca etexMX;/顶点字符串ypefint AdmatrixMAX_VERTNUMMAX_VEREXM;/邻接矩阵tydef stut/定义图eevxsMX_VETENUM;Adjmarix arc;it vexnum，arnum;MGra;int LoateVex(MGrph* ，etex u)/判断权值在矩阵的位置nti;fr(i=0;iG-vnu;+i）f(srcm(G-vexi,u)=0)retrni;rturn -1;voidCreateaph(MGaph *G)/创立邻接矩阵nti
4、，,k,w;rtex a,vb；pritf(请输入顶点数和边数：（用空格隔开）);san(%d，veu,&G-arcnum);rintf(请输入d个顶点的信息:（用空格隔开）n,Gvexnu);for(=0;iG-vexum;+i)scanf（s,G-vexsi);f（i=0;iexnm;+)for(j=0；rcsi=MAX；pin（请输入d条边的两个顶点及权值:（用空格隔开)n,G-exnum);for（k=0；karcnm；+k）af（%s%sd*c,b,w);i=LateVex(G,va);j=LocteVex(,v);G-arcsijGrcsji=；vo kruskal(MrphG)/
5、最小生成树nt stA_VRTEXU，i,;in k=，a=0，b=,mi=G.arsb;for(=0；.eum;+）seti；printf(最小生成树的各条边及权值为:);while（.veum-1)for(i=0;iGexnm;+i)for(j=;jG.vxnum;+j)f（G.arcijin）miG.rcsij;=i;b=j;f(ea!=setb)pritf(%s-%-%,G.vexsa,vexsb,G.acsab)；k+;fo(i=0;Gexnum;i+)f(ti=setb)si=set；mn=GasabG.rcsbaMAX;void main()printf(欢迎建设通信网n)；MGrph G；CreteGraph(&G)；rusal(G);
