实习三求无向连通图生成树

1、实习三求无向连通图的生成树1.需求剖析问题描绘:若要在n个城市之间建设通讯网络，只要要架设n-1条路线即可。怎样以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。基本要求:(1)利用克鲁斯卡尔算法求网的最小生成树，此中，以课本8.7节中的等价类表示结构生成树过程中的连通重量。(2)利用普里姆算法求网的最小生成树。(3)以文本文件形式输出生成树中各条边以及他们的权值。2.设计(1)设计思想：创立毗邻矩阵储存结构。本程序主要分为两个模块：创立邻接矩阵模块，最小生成树模块。创立毗邻矩阵模块：以毗邻矩阵的储存形式创立无向网。最小生成树模块：生成最小生成树，输出其各条边及权值。(2)纲要设计：i

2、nt型LocateVex函数判断权值在矩阵的地点；申明CraeteGraph函数创立毗邻矩阵；申明kruskal函数用于生成最小生成树；申明main函数为程序调用步骤。(3)设计详尽：a.将程序分为两个模块：B.主函数流程图：c.最小生成树流程图(4)调试剖析：-变量没定义就使用解决：定义完变量在使用。-子函数嵌套定义；解决：子函数独自定义，可调用。-使用数组是越界；解决：注意数组的值，注意不可以越界。(5)用户手册：a.主页面：b.输入极点数及边数的信息：c.输入极点信息：d.输入极点及权值：(6)测试结果：输出最小生成树及权值：(7)源程序：#include#include#include

3、#defineMAX100#defineMAX_VERTEXNUM20typedefcharVertexMAX;/极点字符串typedefintAdjmatrixMAX_VERTEXNUMMAX_VERTEXNUM;/毗邻矩阵typedefstruct/定义图VertexvexsMAX_VERTEXNUM;Adjmatrixarcs;intvexnum,arcnum;MGraph;intLocateVex(MGraph*G,Vertexu)/判断权值在矩阵的地点inti;for(i=0;ivexnum;+i)if(strcmp(G-vexsi,u)=0)returni;return-1;voi

4、dCreateGraph(MGraph*G)/创立毗邻矩阵inti,j,k,w;Vertexva,vb;printf(请输入极点数和边数：（用空格分开）n);scanf(%d%d,&G-vexnum,&G-arcnum);printf(请输入%d个极点的信息：（用空格分开）n,G-vexnum);for(i=0;ivexnum;+i)scanf(%s,G-vexsi);for(i=0;ivexnum;+i)for(j=0;jvexnum;+j)G-arcsij=MAX;printf(请输入%d条边的两个极点及权值：（用空格分开）n,G-vexnum);for(k=0;karcnum;+k)sc

5、anf(%s%s%d*c,va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G-arcsij=G-arcsji=w;voidkruskal(MGraphG)/最小生成树intsetMAX_VERTEXNUM,i,j;intk=0,a=0,b=0,min=G.arcsab;for(i=0;iG.vexnum;+i)seti=i;printf(最小生成树的各条边及权值为：n);while(kG.vexnum-1)for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)if(G.arcsijmin)min=G.arcsij;a=i;b=j;if(seta!=setb)printf(%s-%s-%dn,G.vexsa,G.vexsb,G.arcsab);k+;for(i=0;G.vexnum;i+)if(seti=setb)seti=seta;min=