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

实习三 求无向连通图的生成树 需求分析 问题描述: 若要在n个城市之间建设通信网络，只需要架设n-1条路线即可。如何 以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 基本要求: (1)利用克鲁斯卡尔算法求网的最小生成树，其中，以课本8.7节中的等 价类表示构造生成树过程中的连通分量。 (2)利用普里姆算法求网的最小生成树。 (3)以文本文件形式输出生成树中各条边以及他们的权值。 设计 (1)设计思想：创建邻接矩阵存储结构。本程序主要分为两个模块：创建邻接矩阵模块，最小生成树模块。创建邻接矩阵模块：以邻接矩阵的存储形式创建无向网。最小生成树模块：生成最小生成树，输出其各条边及权值。 (2)概要设计：int型 LocateVex函数判断权值在矩阵的位置；声明CraeteGraph函数创建邻接矩阵；声明kruskal函数用于生成最小生成树；声明main函数为程序调用步骤。 (3)设计详细：a.将程序分为两个模块： B.主函数流程图： c.最小生成树流程图 (4)调试分析：--变量没定义就使用 解决：定义完变量在使用。 --子函数嵌套定义； 解决：子函数单独定义，可调用。 --使用数组是越界； 解决：注意数组的值，注意不能越界。 用户手册：a.主页面： b.输入顶点数及边数的信息： c.输入顶点信息： d.输入顶点及权值： (6)测试结果：输出最小生成树及权值： (7)源程序： #includestdio.h #includestdlib.h #includestring.h #define MAX 100 #define MAX_VERTEXNUM 20 typedef char Vertex[MAX];//顶点字符串 typedef int Adjmatrix[MAX_VERTEXNUM][MAX_VERTEXNUM];//邻接矩阵 typedef struct//定义图 { Vertex vexs[MAX_VERTEXNUM]; Adjmatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph* G,Vertex u)//判断权值在矩阵的位置 { int i; for(i=0;iG-vexnum;++i) { if(strcmp(G-vexs[i],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;iG-vexnum;++i) scanf(%s,G-vexs[i]); for(i=0;iG-vexnum;++i) for(j=0;jG-vexnum;++j) G-arcs[i][j]=MAX; printf(请输入%d条边的两个顶点及权值：（用空格隔开）\n,G-vexnum); for(k=0;kG-arcnum;++k) { scanf(%s%s%d*c,va,vb,w); i=LocateVex(G,va); j=LocateVex(G,vb); G-arcs[i][j]=G-arcs[j][i]=w; } } void kruskal(MGraph G)//最小生成树 { int set[MAX_VERTEXNUM],i,j; int k=0,a=0,b=0,min=G.arcs[a][b]; for(i=0;iG.vexnum;++i) set[i]=i; printf(最小生成树的各条边及权值为：\n); while(kG.vexnum-1) { for(i=0;iG.vexnum;++i) for(j=0;jG.vexnum;++j) if(G.arcs[i][j]min) { min=G.arcs[i][j]; a=i; b=j; } if