城市通信网络建设系统

1、数据结构课程设计题目：城市通信网络建设系统班级：*姓名：*学号：1111111111指导教师：AAAAAAAAA完成日期：2015年6月13日1 .需求分析1.1 问题描述通信设施的安全保障是安全生产管理工作的一项重要内容。随着通信网络的不断扩大和各种先进的通信方式日益增多相应的通信设施也在快速扩展，在不同的环境、不同的地域受到各种客观条件的影响和破坏(包括自然因素和人为因素)以及通信设施在使用过程中的老化都会对全程全网的通信质量造成不同程度的影响。因此，采用通信设施安全保障计算机管理系统实现全区通信设施的集中管理，对保障通信设施安全，提高维护工作效率，及时发现与处理隐患问题，增强抵抗灾害能力

2、，特别是在实现管理工作的系统化、正规化、规范化方面是非常必要的。如何在最小的经济条件下达到利益最大化，是所有公司、企业已经政府部门一直所探讨和解决的问题。对于城市通信管理系统来说，若要在n个城市之间建设通信网络，只需要架设n-1条通信线路即可，建立最小生成树即能实现以最低的经济代价建设这个通信网。1.2 基本任务通过用户调查分析及实际需求，系统需要实现如下基本任务：(1)在纸上模拟设计n个城市的网络平面图，城市数不少于20个，相同的的城市数不少于2(n-1),顶点表示各城市，边表示城市间的距离；(2)编写算法，求解最小代价通信网络；(3)输出该通信网络中各边及其权值；n个城市间的线路连接属于图

3、的结构，要构建最经济的通信网络，即是构建图的生成树。把城市间的线路关系看成是图。城市间的距离即是图的权值。利用prim算法或kruskal算法即可求出最小生成树。2 .概要设计为了完成需求分析的基本任务，主要从以下3个方面进行设计：2.1 主界面设计为了使程序界面更加友好，建立了interface函数和choice函数，即欢迎界面以及实现用户可以按数字键选择相应的功能。欢迎界面如下图：中 CiU«T5'|Admii nEtnat 口、口 g kt <?pk»c5"j .exe15通信网鲤本信息井萼情息存楣到文件中信息显示到屣虹&怯WI褊请输入

4、您费选择的选:2.2 数据结构设计若要在n个城市之间建设通信网络，只需要架设n-1条通信线路即可。所以，将一个现实的经济问题，转变为一个求最小生成树的问题。本系统软件采用经典算法prim算法和kruskal算法实现求最小生成树，从而获取最经济的通信路径。2.3 系统功能设计系统建立了interface函数和choice函数，其功能如下：( 1) interface函数：使用户更清晰看到程序的主体，使得程序界面更为直观。程序如下：voidinterface()/初始界面printf("n");printf("最小生成树的应用n");printf("

5、;通信网络建设问题n");printf("MadeBy董卓琴Version1.0n");printf("n");printf("n");printf("n");printf("n"printf("n");printf("1.输入通信网络基本信息并将信息存储到文件中n");printf("2.将网络基本信息显示到屏幕上n");printf("3.用kruskal算法算出最短路径，并将结果存储到文件中n");p

6、rintf("4.用prim算法算出最短路径，并将结果存储到文件中n");printf("5.退出n");printf("n");printf("n");printf("ttt请输入您要选择的选项(1-5):n");( 2) choice函数：为用户提供了方便，用户可以通过按数字键来选择相应的功能。程序如下：voidchoice()/控制选项函数MGraphG=MGraph();intc;interface();std:cin>>c;while(c)switch(c)case1:sy

7、stem("cls");system("color1b");printf("n");printf("ntt*欢迎使用 *");Welcom_to_Use");printf("n*");printf(" n");printf(" n");printf(" n");G=SaveGraph(G);system("cls");interface();/system("PAUSE"); std:c

8、in>>c;continue;case 2:system("cls");system("color 1c");printf(" n");printf(" ntt*欢迎使用 *");printf(" nWelcom_to_Use");printf("n*printf("n*");printf("n");printf("ttt下面显示的是通信网络的基本信息n");printf("n");G=Save

9、Graph(G);G=print(G);printf("nttt按任意键返回n");c=getchar();/c=getchar();system("cls");interface();/system("PAUSE");std:cin>>c;continue;case3:system("cls");system("color1e");printf("n");printf("ntt*printf("n欢迎使用*");Welcom_to_

10、Use");printf("n*");printf("n");printf("n");printf("n");G=SaveGraph(G);prim(G,G.vexs0);*printf("tt*结果存入KruskalResult.dat中，按任意键返回*n");c=getchar();c=getchar();system("cls");interface();system("PAUSE");std:cin>>c;continue;c

11、ase4:system("cls");system("color1d");printf("n");printf("ntt*printf("n欢迎使用*");Welcom_to_Use");printf("n*");printf("n");printf("n");printf("n");G=SaveGraph(G);G=kruskal(G);printf("tt*n");c=getchar();c=

12、getchar();system("cls");interface();system("PAUSE");std:cin>>c;结果存入PrimResult.dat中，按任意键返回continue;case5:return;3.模块设计3.1 模块设计系统主要包含主程序模块和其它操作模块。其调用关系如下图所示。(l)CreateGraph(G);/创建图模块(2)SaveGraph(G);/存储图模块(3)Print(G);/输出图模块(4)Kruskal(G);/kruskal算法求最小生成树模块Kruskal算法的基本思想是：1 、若网络G

13、的边数en1,则G即为所求的最小生成树，否则，一定有e>n-1.2 、将网络的e条边按权值自小到大顺序排列。3 、将网络G中的边都去掉，只留下n个孤立顶点作为初始的最小生成树T,再按边的排放顺序逐个考察，若与当前E(T)中的边不构成圈，便将它加入到边集E(T),直至E(T)中边数满n-1为止。(5)Prim(G);/prim算法求最小生成树模块Prim算法是另一种求最小生成树的方法，它的基本思想是按权值局部最小逐次将顶点和边加入到T中，直至V(T)，黄n个顶点为止。Prim算法步骤为：1 、设最小生成树T的V(T)和E(T)均为空。2、从顶点集V(G)中任取一顶点加到顶点集V(T)中。3

14、、在与V(T)中各顶点相关的所有边中，取一条权值最小的边(Vi,Vj)，其中，Vi包含于V(T),Vj包含于V(T)。4、(Vi,Vj)加入到E(T)中，将顶点Vj加入到V(T)中。5、若V(T)已满n个顶点，则算法终止，否则转步骤(3)。2 .3系统模块之间的调用关系系统的5个子模块之间的主要调用关系如下图所示：4.1数据结构设计系统采用邻接矩阵存储信息，定义如下：/图的数据结构typedefstructMGraph/建立图MGraph()memset(vexs,0,MAX_VERTEX_NUM);VertexvexsMAX_VERTEX_NUM;城市名称intAdjMatrixarcs;/

15、网络条数intvexnum;/图的当前顶点数(城市总数)intarcnum;/图的当前弧数(网络总数)MGraph;/记录从顶点集U到V-U的代价最小的边的辅助数组定义typedefstructTemp辅助数组Temp()lowcost=0;Vertexadjvex;/当前点intlowcost;/权值closedgeMAX_VERTEX_NUM;typedefstructCityNumberCityNumber()memset(cityNam,0,1024);charcityNam1024;CityNum;CityNum*Hometown=newCityNum20;若G中存在顶点u,则返回该

16、顶点在图中位置；否则返回-1。#include<stdio.h>intLocateVex(MGraphG,Vertexu)inti;for(i=0;i<G.vexnum;+i)if(strcmp(u,G.vexsi)=0)returni;return-1;4.2系统主要模块设计4.2.1 CreateGraph函数1)创建邻接矩阵以存储图的内容。2)填充矩阵，即输入城市间网络的状况，以方便使用prim算法或kruskal算法求出最经济的架设方法。程序如下：/采用数组(邻接矩阵)表示法,构造无向网G。MGraphCreateGraph(MGraph&G)inti=0,j

17、=0,k=0,w=0;Vertexva,vb;/路径的两个节点printf("nntt*建立城市间网络信息*");printf("请输入城市的总数:n");scanf("%d",&G.vexnum);printf("请输入城市间的网络数:n");scanf("%d",&G.arcnum);printf("请输入%d个城市的名称(<%d个字符):n",G.vexnum);for(i=0;i<G.vexnum;+i)/构造顶点向量scanf("

18、;%s",G.vexsi);for(i=0;i<G.vexnum;+i)/初始化邻接矩阵for(j=0;j<G.vexnum;+j)G.arcsij=65535;/65535为无穷大printf("请输入%d条网络的两个城市信息城市1和城市2的距离(以空格作为间隔):n",G.arcnum);for(k=0;k<G.arcnum;+k)scanf("%s%s%d",va,vb,&w);/输入城市1城市2名称及其距离i=LocateVex(G,va);/定位权值位置j=LocateVex(G,vb);G.arcsij=G

19、.arcsji=w;/对称returnG;4.2.2 SaveGraph函数1 )为了避免每次都重复输入信息，用文件存储图的内容。2)如果没有文件则建立文件，并把图的内容存储到文件中。3)如果文件存在，则从文件中读取图的内容到内存，以便完成其他操作。程序如下：MGraphSaveGraph(MGraphG)/输入内容存储在smalltree.datinti,j;FILE*fp;fp=fopen("smalltree.dat","rt");if(fp=NULL)G=CreateGraph(G);fp=fopen("smalltree.dat&qu

20、ot;,"wt");fprintf(fp,"%dn",G.vexnum);/存城市树fprintf(fp,"%dn",G.arcnum);/存网络数for(i=0;i<G.vexnum;+i)fprintf(fp,"%stn",G.vexsi);/存城市名称for(i=0;i<G.vexnum;+i)/存储邻接矩阵for(j=0;j<G.vexnum;+j)if(G.vexsi=G.vexsj).vexsj,.vexsj,G.arcsij=0;/到它自己fprintf(fp,"%s_%s

21、_%dn",G.vexsi,GG.arcsij);elsefprintf(fp,"%s_%s_%dn",G.vexsi,GG.arcsij);rewind(fp);std:cout<<"存储成功！。输入任意键返回."<<std:endl;charc=getchar();else/从文件中读取网的信息存到内存中printf("tt*正在读取文件中*n");fscanf(fp,"%dn",&G.vexnum);fscanf(fp,"%dn",&G.a

22、rcnum);chartempBuffer1024;memset(tempBuffer,0,1024);for(i=0;i<G.vexnum;+i)fgets(tempBuffer,1023,fp);strcpy(Hometowni.cityNam,tempBuffer);charCityA1024;intLenth=0;memset(CityA,0,1024);for(i=0;i<G.vexnum;+i)for(j=0;j<G.arcnum;+j)fscanf(fp,"%s",&CityA);intn=0;chartempCityName1024

23、;memset(tempCityName,0,1024);while(CityAn!='_')tempCityNamen=CityAn;n+;strcpy(G.vexsi+G.vexnum,tempCityName);n+;memset(tempCityName,0,1024);intnum=0;while(CityAn!='_')tempCityNamenum=CityAn;n+;num+;strcpy(G.vexsi+G.vexnum+1,tempCityName);intnumint=0;n+;memset(tempCityName,0,1024);whi

24、le(CityAn!='0')tempCityNamenumint=CityAn;n+;numint+;intX=1;Lenth=0;for(n=numint-1;n>=0;n-)intintkeynum=0;switch(tempCityNamen)case'0':intkeynum=0;break;case'1':intkeynum=1;break;case'2':intkeynum=2;break;case'3':intkeynum=3;break;case'4':intkeynum=4

25、;break;case'5':intkeynum=5;break;case'6':intkeynum=6;break;case'7':intkeynum=7;break;case'8':intkeynum=8;break;case'9':intkeynum=9;break;Lenth+=intkeynum*X;X=X*10;G.arcsij=Lenth;printf("tt*读取成功.t*n");fclose(fp);returnG;4.2.3 print函数Print函数完成输出功能，将内存中

26、图的内容输出到屏幕上程序如下：MGraphprint(MGraphG)/将输入的网络基本信息打到屏幕上inti,j;printf("城市总数:%dt",G.vexnum);printf("网络条数:%dn",G.arcnum);printf("城市名称:tn");for(i=0;i<G.vexnum;i+)/printf("%s_",G.vexsi);std:cout<<Hometowni.cityNam;printf("n");printf("各个城市间的距离:n&

27、quot;);printf("n");printf("n");for(i=0;i<G.vexnum;+i)for(j=0;j<G.vexnum;+j)printf("%s_%s_距离:%d公里n",G.vexsi+G.vexnum,G.vexsj+G.vexnum,G.arcsij);std:cout<<"输入任意键返回."<<std:endl;charc=getchar();returnG;4.2.4 kruskal函数用kruskal算法求出最小生成树，即最经济的假设方案程序

28、如下：MGraphkruskal(MGraphG)/结果存储在KruskalResult.datintsetMAX_VERTEX_NUM,i,j;intk=0,a=0,b=0,min=G.arcsab;FILE*ffp;ffp=fopen("KruskaiResult.dat","wt");for(i=0;i<G.vexnum;i+)seti=i;printf("最短网络路径为:n");while(k<G.vexnum-1)for(i=0;i<G.vexnum;+i)/从G.arcsij中找到权值最小的for(j=i

29、+1;j<G.vexnum;+j)if(G.arcsij<min)min=G.arcsij;/min中存最小权值a=i;b=j;if(seta!=setb)/如果a和b值不同则输出printf("%s-%st距离:%dn",G.vexsa,G.vexsb,G.arcsab);/输出生成树各边fprintf(ffp,"%s-%sn",G.vexsa,G.vexsb);k+;for(i=0;i<G.vexnum;i+)/输出后变成相同值，下次将不会输出if(seti=setb)seti=seta;min=G.arcsab=G.arcsba=

30、65535;/输出过的权值变为最大值rewind(ffp);fclose(ffp);returnG;4.2.5 prim函数用prim算法求出最小生成树，即最经济的假设方案程序如下：/用普里姆算法从第u个顶点出发构造网G的最小生成树输出T的各条边voidprim(MGraphG,Vertexu)/结果存储在PrimResult.dat中inti,j,k=0;closedgeclose;FILE*fpp;fpp=fopen("PrimResult.dat","wt");k=LocateVex(G,u);for(j=0;j<G.vexnum;+j)/辅

31、助数组初始化strcpy(closej.adjvex,u);closej.lowcost=G.arcskj;closek.lowcost=0;/初始,U=uprintf("最短网络路径为:n");for(i=1;i<G.vexnum;+i)/选择其余G.vexnum-1个顶点k=minimum(G,close);/求出T的下一个结点：第K顶点printf("(%s-%s)n",closek.adjvex,G.vexsk);fprintf(fpp,"%s-%sn",closek.adjvex,G.vexsk);/输出生成树的边cl

32、osek.lowcost=0;/第K顶点并入U集for(j=0;j<G.vexnum;+j)if(G.arcskj<closej.lowcost)/新顶点并入U集后重新选择最小边strcpy(closej.adjvex,G.vexsk);closej.lowcost=G.arcskj;rewind(fpp);fclose(fpp);5调试分析系统主界面运行如图1所示。各子功能测试运行结果如下运行程序，出现欢迎界面，见下图：5.1城市间网络信息的建立5.2显示通信网络的基本信息CUqernAdrminitratorVD&sktopkcsj.exem>£MXMm

33、m;xm;hm34-km-m;m-k1口j*f|mmmmkX-m;m-Mk-mm-mm-Xm*£-mMmmm.IJeIcon_to_IJee-r«,1-r-!i_r»-ri-r!«-ri_ri»_ri-cT-rui-rrraF面显炉的是通信网络的基本信息MMXXKWJKMWXMHKJC或能堂 麻市包NJ不二网络条数;6正在读取又件中 读取咸访八.19悟个城市间的距离,BtkAkAR3Z4ZABLk%5-5竺33s55/-z2550166离离离离m=m-.一三.里里里里里里杰里里里公公里心公里里里公公35公里公公&104-2&60

34、56514Htl»41s3jzrtnlj*z±z3s6*£64s59f25556202165nF-UEMF-nujnuj33HSHS3OH355lELtiLtM.1s包/包fkfkrFTT6&00&aE前菽箭备刘备登如舒苣即菽菽前期歹士外歌.七s=升附巨巨巨巨巨LULULUUJUJUJUJUJlOJOJLDJLDJLQJU1JLULU巨隹;J1-rrrrrrrnr-_!,£?s_pnr-nc-nL-M-E-HE-He-n_L-n_L-ZZXHZZZXHZZZXHZZZXHZZZXG一_cz_wss-s-c-c-w-s-s-c-c-w-ss

35、-c-c_w-s-sG-Aft.ICLCD5.3查询最短网络路径6 .用户使用说明1、运行程序，出现欢迎界面；2、按1进入输入系统，如果文件没有存储城市网络内容，则由用户从键盘读入，读入后自动保存到文件中，按任意键即可返回欢迎界面；3、如果文件内已经存储了城市网络内容，则显示文件已保存到文件中，按任意键返回；4、输入2可以在屏幕上输出存储在文件内的城市间网络信息，显示完毕后按任意键可返回欢迎见面；5、按3和4分别可实现kruskal算法和prim算法求出最小生成树，即最低经济代价建设通信网络（距离最短的最经济），显示完毕后按任意键返回欢迎界面；6、按5退出程序。7 .参考文献数据结构理论与实践

36、杨永斌（核心算法prim算法以及kruskal算法来源于此）数据结构（C语言）实践教程胡元义数据结构严蔚敏、吴伟民«VisualC+课程设计案例精选与编程指导陈清华、朱红8 .对所设计的软件进行自我评价，如创新点、未解决的问题等情况说明：1、对图的逻辑结构及存储结构有了更深刻的认识；2、对prim算法和kruskal算法亦有了更深刻的认识；3、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力，深入了解了模块化的程序设计步骤；4、kruskal算法应该用堆排序然后再找路径，但未能实现；5、输入方面如果没有将网络信息存入文件，由键盘输入信息时，如果手误输错了无法更改，只能

37、重新输入，而且如果输入中文，最后显示时会出现乱码，只能用英文输入；6、kruskal算法的实现仍有问题，结果存在错误，而且只能实行到第三步，到第四步时会出现程序关闭的提醒；9、程序源代码：#include<stdlib.h>#include<string.h>#include<iostream>#defineMAX_VERTEX_NUM20/最大顶点个数#defineMAX_NAME3/顶点字符串的最大长度+1typedefintintAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefcharVertexMAX_NAM

38、E;/邻接矩阵的数据结构/图的数据结构typedefstructMGraph/建立图MGraph()memset(vexs,0,MAX_VERTEX_NUM);VertexvexsMAX_VERTEX_NUM;/城市名称intAdjMatrixarcs;/网络条数intvexnum;/图的当前顶点数(城市总数)intarcnum;/图的当前弧数(网络总数)MGraph;/记录从顶点集U到V-U的代价最小的边的辅助数组定义typedefstructTemp/辅助数组Temp()lowcost=0;Vertexadjvex;/当前点intlowcost;/权值closedgeMAX_VERTEX_

39、NUM;typedefstructCityNumberCityNumber()memset(cityNam,0,1024);charcityNam1024;CityNum;CityNum*Hometown=newCityNum20;/若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。#include<stdio.h>intLocateVex(MGraphG,Vertexu)inti;for(i=0;i<G.vexnum;+i)if(strcmp(u,G.vexsi)=0)returni;return-1;/采用数组(邻接矩阵)表示法,构造无向网G。MGraphCreat

40、eGraph(MGraph&G)inti=0,j=0,k=0,w=0;Vertexva,vb;/路径的两个节点printf("nntt*建立城市间网络信息*");printf("请输入城市的总数:n");scanf("%d",&G.vexnum);printf("请输入城市间的网络数:n");scanf("%d",&G.arcnum);printf("请输入d个城市的名称(<%d个字符):n",G.vexnum);for(i=0;i<G.v

41、exnum;+i)/构造顶点向量scanf("%s",G.vexsi);for(i=0;i<G.vexnum;+i)/初始化邻接矩阵for(j=0;j<G.vexnum;+j)G.arcsij=65535;/65535为无穷大printf("请输入d条网络的两个城市信息城市1和城市2的距离(以空格作为间隔):n",G.arcnum);for(k=0;k<G.arcnum;+k)scanf("%s%s%d",va,vb,&w);/输入城市1城市2名称及其距离i=LocateVex(G,va);/定位权值位置j=

42、LocateVex(G,vb);G.arcsij=G.arcsji=w;/对称returnG;MGraphSaveGraph(MGraphG)/输入内容存储在smalltree.datinti,j;FILE*fp;fp=fopen("smalltree.dat","rt");if(fp=NULL)G=CreateGraph(G);fp=fopen("smalltree.dat","wt");fprintf(fp,"%dn",G.vexnum);/存城市树fprintf(fp,"%dn&

43、quot;,G.arcnum);/存网络数for(i=0;i<G.vexnum;+i)fprintf(fp,"%stn",G.vexsi);/存城市名称for(i=0;i<G.vexnum;+i)/存储邻接矩阵for(j=0;j<G.vexnum;+j)if(G.vexsi=G.vexsj)G.arcsij);G.arcsij);G.arcsij=0;/到它自己fprintf(fp,"%s_%s_%dn",G.vexsi,G.vexsj,elsefprintf(fp,"%s_%s_%dn",G.vexsi,G.vex

44、sj,rewind(fp);std:cout<<"存储成功！。输入任意键返回."<<std:endl;charc=getchar();else/从文件中读取网的信息存到内存中31printf("tt*正在读取文件中*n");fscanf(fp,"%dn",&G.vexnum);fscanf(fp,"%dn",&G.arcnum);chartempBuffer1024;memset(tempBuffer,0,1024);for(i=0;i<G.vexnum;+i)fget

45、s(tempBuffer,1023,fp);strcpy(Hometowni.cityNam,tempBuffer);charCityA1024;intLenth=0;memset(CityA,0,1024);for(i=0;i<G.vexnum;+i)for(j=0;j<G.arcnum;+j)fscanf(fp,"%s",&CityA);intn=0;chartempCityName1024;memset(tempCityName,0,1024);while(CityAn!='_')tempCityNamen=CityAn;n+;st

46、rcpy(G.vexsi+G.vexnum,tempCityName);n+;memset(tempCityName,0,1024);intnum=0;while(CityAn!='_')tempCityNamenum=CityAn;n+;num+;strcpy(G.vexsi+G.vexnum+1,tempCityName);intnumint=0;n+;memset(tempCityName,0,1024);while(CityAn!='0')tempCityNamenumint=CityAn;n+;numint+;intX=1;Lenth=0;for(n=

47、numint-1;n>=0;n-)intintkeynum=0;switch(tempCityNamen)case'0':intkeynum=0;break;case'1':intkeynum=1;break;case'2':intkeynum=2;break;case'3':intkeynum=3;break;case'4':intkeynum=4;break;case'5':intkeynum=5;break;case'6':intkeynum=6;break;case&#

48、39;7':intkeynum=7;break;case'8':intkeynum=8;break;case'9':intkeynum=9;break;Lenth+=intkeynum*X;X=X*10;G.arcsij=Lenth;printf("tt*读取成功.t*n");fclose(fp);将输入的网络基本信息打到屏幕上returnG;MGraphprint(MGraphG)/inti,j;printf("城市总数:%dt",G.vexnum);printf("网络条数:%dn",G.a

49、rcnum);printf("城市名称:tn");for(i=0;i<G.vexnum;i+)/printf("%s_",G.vexsi);std:cout<<Hometowni.cityNam;printf("n");printf("各个城市间的距离:n");printf("n");printf("n");for(i=0;i<G.vexnum;+i)for(j=0;j<G.vexnum;+j)printf("%s_%s_距离:%d公里

50、n",G.vexsi+G.vexnum,G.vexsj+G.vexnum,G.arcsij);std:cout<<"输入任意键返回."<<std:endl;charc=getchar();returnG;MGraphkruskal(MGraphG)/结果存储在KruskalResult.datintsetMAX_VERTEX_NUM,i,j;intk=0,a=0,b=0,min=G.arcsab;FILE*ffp;ffp=fopen("KruskaiResult.dat","wt");for(i=0;

51、i<G.vexnum;i+)seti=i;printf("最短网络路径为:n");while(k<G.vexnum-1)for(i=0;i<G.vexnum;+i)/从G.arcsij中找到权值最小的for(j=i+1;j<G.vexnum;+j)if(G.arcsij<min)min=G.arcsij;/min中存最小权值a=i;b=j;if(seta!=setb)/如果a和b值不同则输出printf("%s-%st距离:dn",G.vexsa,G.vexsb,G.arcsab);输出生成树各边fprintf(ffp,&q

52、uot;%s-%sn",G.vexsa,G.vexsb);k+;for(i=0;i<G.vexnum;i+)/输出后变成相同值，下次将不会输出if(seti=setb)seti=seta;输出过的权值变为最大值min=G.arcsab=G.arcsba=65535;/rewind(ffp);fclose(ffp);returnG;/求closedge结构体中lowcost的最小正值intminimum(MGraphG,closedgeclose)inti=0,j,k,min;while(!closei.lowcost)i+;min=closei.lowcost;/第一个不为0的

53、值k=i;for(j=i+1;j<G.vexnum;j+)if(closej.lowcost>0&&min>closej.lowcost)min=closej.lowcost;k=j;returnk;/用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边voidprim(MGraphG,Vertexu)/结果存储在PrimResult.dat中inti,j,k=0;closedgeclose;FILE*fpp;fpp=fopen("PrimResult.dat","wt");k=LocateVex(G,u)

54、;for(j=0;j<G.vexnum;+j)/辅助数组初始化strcpy(closej.adjvex,u);closej.lowcost=G.arcskj;closek.lowcost=0;/初始,U=uprintf("最短网络路径为:n");for(i=1;i<G.vexnum;+i)/选择其余G.vexnum-1个顶点k=minimum(G,close);求出T的下一个结点：第K顶点printf("(%s-%s)n",closek.adjvex,G.vexsk);fprintf(fpp,"%s-%sn",closek

55、.adjvex,G.vexsk);/输出生成树的边closek.lowcost=0;/第K顶点并入U集for(j=0;j<G.vexnum;+j)if(G.arcskj<closej.lowcost)/新顶点并入U集后重新选择最小边strcpy(closej.adjvex,G.vexsk);closej.lowcost=G.arcskj;rewind(fpp);fclose(fpp);voidinterface()/初始界面printf("n");printf("最小生成树的应用n");printf("通信网络建设问题n");printf("Ma