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

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

2、概要设计：int型LocateVex函数判断权值在矩阵的位置；声明CraeteGraph 函数创建邻接矩阵；声明kruskal函数用于生成最小生成树；声明main函数为程 序调用步骤。(3)设计详细：a.将程序分为两个模块：B.主函数流程图:c.最小生成树流程图(4)调试分析:(5)用户手册:-变量没定义就使用-子函数嵌套定义；-使用数组是越界； a.主页面：解决：定义完变量在使用。解决：子函数单独定义，可调用。解决：注意数组的值，注意不能越界(用空格隔开)网和 I 设顶 人 迎输 次全月b.输入顶点数及边数的信息:阿迎建逡通信网请输入演第额和边数；（用空格隔开）3 3C.输入顶点信息:欢迎建

3、设通信网请输入熊殿和辿数;（用空格隔开）:扁人?个顶点的信心（用空格隔开）12 3d.输入顶点及权值:欢迎建设通信网手输入顶售薮和边数：（用空格隔开） 褊个顶点的信息，,用空格隔开） 福输I,条边的两个顶点及权值；（用空格隔开）12 113 3（6）测试结果：输出最小生成树及权值:欢迎建设遹值网请输入顶苫数和边数：（用空格隔开）褐I入3个顶点的信息一 （用空格隔开）Lil13条边的两个顶点及权值；（用空格隔开） 12 113 3朗是成树的各条边及权值为；1-2-117-3源程序:#include<stdio.h>#include<stdlib.h>#include<

4、;string.h>#define MAX 100#define MAX_VERTEXNUM 20typedef char VertexMAX;/ 顶点字符串typedef int AdjmatrixMAX_VERTEXNUMMAX_VERTEXNUM; 令口接矩阵typedef struct/淀义图Vertex vexsMAX_VERTEXNUM;Adjmatrix arcs;int vexnum,arcnum;MGraph;int LocateVex(MGraph* G,Vertex u)/判断权值在矩阵的位置 int i;for(i=0;i<G->vexnum;+i)i

5、f(strcmp(G->vexsi,u)=0) return i;return -1;void CreateGraph(MGraph *G)创建邻接矩阵int i,j,k,w;Vertex va,vb;printf("请输入顶点数和边数：(用空格隔开)n");scanf("%d%d",&G->vexnum,&G->arcnum);printf("请输入%d个顶点的信息：(用空格隔开)n",G->vexnum);for(i=0;i<G->vexnum;+i)scanf("%s

6、”,G->vexsi);for(i=0;i<G->vexnum;+i)for(j=0;j<G->vexnum;+j)G->arcsij=MAX;printf("请输入%d条边的两个顶点及权值：(用空格隔开)n",G->vexnum); for(k=0;k<G->arcnum;+k)scanf("%s%s%d*c”,va,vb,&w);i=LocateVex(Gva);j=LocateVex(Gvb);G->arcsij=G->arcsji=w;void kruskal(MGraph G)/最

7、小生成树int setMAX_VERTEXNUM,i,j;int k=0,a=0,b=0,min=G.arcsab;for(i=0;i<G .vexnum;+i)seti=i;printf("最小生成树的各条边及权值为：n");while(k<G.vexnum-1) for(i=0;i<G .vexnum;+i)for(j=0;j<G .vexnum;+j)if(G.arcsij<min) min=G.arcsij;a=i;b=j；if(seta!=setb)printf("%s-%s-%dn",G.vexsa,Gvexsb,G.arcsab); k+;for(i=0;G .vexnum;i+)if(seti=setb)set