数据结构课程设计-最小生成树问题.docx

实习5、最小生成树问题一、需求分析1.问题描述若要在n个城市间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。2.基本要求(1)利用克鲁斯卡尔算法求网的最小生成树。(2)实现教科书6.5节中定义的抽象数据类型mfset。以此表示构造生成树过程中的连通分量。(3)以文本形式输出生成树中各边以及它们的权值。3.测试数据 4. 实现提示通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用c语言提供的随机函数产生。图的存储结构的选取应和所做操作相适应。为了便于选择权值最小的边，此题的存储结构既不用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。二、概要设计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存在。操作结果：输出图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(igraph *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+) printf(请输入第%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;ivexnum;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=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.endvex; 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;/和以前的节点比较，如果边的权值小，则选取已有的结点中权值最小的边 void 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 min