《数据结构课程设计-最小生成树问题.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计-最小生成树问题.docx（7页珍藏版）》请在金锄头文库上搜索。
1、实习5、最小生成树问题一、需求分析1.问题描述若要在n个城市间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。2.基本要求(1)利用克鲁斯卡尔算法求网的最小生成树。(2)实现教科书6.5节中定义的抽象数据类型MFSet。以此表示构造生成树过程中的连通分量。(3)以文本形式输出生成树中各边以及它们的权值。3.测试数据 4. 实现提示通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机函数产生。图的存储结构的选取应和所做操作相适应
2、。为了便于选择权值最小的边，此题的存储结构既不用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。二、概要设计ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。 数据关系R：R=VRVR=|v,wV且P(v,w), 表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 基本操作： CreateUDN( *G)操作结果：创建无向图。MiniSpanTree(G,minedge)（使用克里斯卡尔算法始终调试不成功只好改用普利姆算法）初始条件：图G存在。操作结果：求图G的最小生成树。PrintMinEdge(G,minedge)初始条件：图G存在。
3、操作结果：输出图G的最小生成树。ADT Graph三、详细设计（源代码）（使用C语言时指针参数传递总是出问题只好改用C+语言）#include #include #define MAX 10/本程序设最大顶点数为10typedef struct int vexnum;/点数量 int arcnum;/边数量 int arcsMAXMAX;/边存储 char vexsMAX;/点存储iGraph;typedef struct close int adjvex; int endvex; int lowcost;/最小权值*closedge,closedges;void CreateUDN(iGra
4、ph *G)/创建无向图 int i,j,m,k,l,cost; char name1,name2; printf(请输入顶点数和边数（注意：边数大于或等于顶点数）：n); scanf(%d %d,&G-vexnum,&G-arcnum); getchar(); printf(请输入各个顶点名字：n); for(i=0;ivexnum;i+) scanf(%c,&G-vexsi); getchar(); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) G-arcsij=100; /初始化边的权值此程序设100为最大值 for(i=0;iarcnum;i+) pr
5、intf(请输入第%d条边（输入格式为：端点1-端点2:权值）：n,i+1); scanf(%c-%c:%d,&name1,&name2,&cost); getchar(); for(j=0;jvexnum;j+)/在表中查找点 if(name1=G-vexsj) k=j; for(m=0;mvexnum;m+)/在表中查找点 if(name2=G-vexsm) l=m; if(k=l)/两个点如果相同，报错 i-; printf(输入错误的数据,请重新输入n); continue; G-arcskl=cost;/无向边赋权值 G-arcslk=cost; /使输入的边赋值 for(i=0;i
6、vexnum;i+) for(j=0;jvexnum;j+) if(i=j) G-arcsij=0;/如果端点相同，则不存在边void MiniSpanTree(iGraph G,closedge &minedge) /求最小生成树 int i,j,k,z; int temp; int currentmin; k=0; minedge=(closedge)malloc(G.vexnum+1)*sizeof(closedges); for(j=1;jG.vexnum;j+) minedgej-1.adjvex=k; minedgej-1.endvex=j; minedgej-1.lowcost=
7、G.arcskj; for(i=0;iG.vexnum-1;i+) currentmin=minedgei.lowcost; k=i; for(j=i+1;jG.vexnum-1;j+) if(minedgej.lowcostcurrentmin) currentmin=minedgej.lowcost; k=j; /交换第k个元素和第i个元素 temp=minedgei.adjvex; minedgei.adjvex=minedgek.adjvex; minedgek.adjvex=temp; temp=minedgei.endvex; minedgei.endvex=minedgek.en
8、dvex; minedgek.endvex=temp; temp=minedgei.lowcost; minedgei.lowcost=minedgek.lowcost; minedgek.lowcost=temp; for(j=i+1;jG.vexnum-1;j+) z=minedgei.endvex;/Z为新找到的顶点 k=minedgej.endvex; if(k!=z) if(G.arcszkminedgej.lowcost) minedgej.adjvex=z; minedgej.lowcost=G.arcszk;/和以前的节点比较，如果边的权值小，则选取已有的结点中权值最小的边 v
9、oid PrintMinEdge(iGraph G,closedge minedge)/输出所求最小生成树 int i,sum; sum=0; printf(最小生成树对应的边为n); for(i=0;iG.vexnum-1;i+) printf(%c-%c:权值为：%dn,G.vexsminedgei.adjvex,G.vexsminedgei.endvex,minedgei.lowcost); sum=sum+minedgei.lowcost; printf(最小生成树的权值为：%d,sum);int main()/主函数 printf(*n); printf(* *n); printf(* 最小生成树问题 *n); printf(* *n); printf(*n); iGraph G; closedge minedge; CreateUDN(&G);/输入无向网 printf(n); MiniSpanTree(G,minedge);/求最小生成树 PrintMinEdge(G,minedge);/输出最小生成树 printf(n); return 0;四、调试分析编译环境为CodeBlocks。
