数据结构课程设计求最小生成树

##大学数据结构课程设计报告题目：图的最小生成树院（系）：学生姓名:班级：学号:起迄日期:指导教师:2011—2012年度第2学期指导教师评语：成绩：签名：年月日一、需求分析1.问题描述：设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。该题目需要运用最小生成树来解决。最小生成树的代价之和最小，所以是一种最经济的架设方法。2.基本功能该程序是解决城市间架设网络问题的，采用邻接表与邻接矩阵对构造的图进行存储，用普利姆与克鲁斯卡尔算法进行求解。3.输入输出首先输入顶点的个数以及边的个数，格式如:46。然后输入边的权值，格式如：ab1。输出分为四种输出，输出邻接表，邻接矩阵，普利姆算法求得的最小生成树，克鲁斯卡尔求得的最小生成树。最小生成树的格式为：顶点名顶点名权值。二、概要设计1.设计思路：问题的解决分别采用普利姆算法已经克鲁斯卡尔算法。1）普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，依此类推，如果到达最后一个则返回上一个顶点。2）克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，依此类推，最终要有个判断是是否生成环，不生成则得到克鲁斯卡尔的最小生成树。2.数据结构设计：1.抽象数据类型如下：ADTGraph{数据对象V：v是具有相同特征的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={v,w|v,w属于v且p（v,w）表示从v到w的弧，谓词p（v,w）定义了弧v,w的意义或信息}基本操作：1)GreatGraph（&G,V,VR）；初始条件：V是图的顶点集，VR是图中弧的集合。操作条件：按V和VR的定义构造图G。2）LocateVex（G,u）；初始条件：图G存在，u和G中顶点有相同的特征。操作条件：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。2.存储结构typedefstructArcCell{intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];//定义一个顶点数组AdjMatrixarcs;intvexnum,arcnum;}MGraph_L;typedefstructarcnode//弧结点{intadjvex;//该弧指向的顶点的位置structarcnode*nextarc;//弧尾相同的下一条弧char*info;//该弧信息}arcnode;typedefstructvnode//邻接链表顶点头接点{chardata;//结点信息arcnode*firstarc;//指向第一条依附该结点的弧的指针}vnode,adjlist;3.软件结构设计：三、详细设计开始创建一个图功能选择1.建立邻接矩阵2.建立邻接表3.PRIM算法4.kruscal算法结束1．主函数和其他函数的伪码算法主函数：voidmain(){algraphgra;MGraph_LG;inti,j,d,g[20][20];chara='a';d=creatMGraph_L(G);creatadj(gra,G);cout**********************************endl;cout**1。用邻接矩阵存储：*************endl;cout**2。用邻接表存储：***************endl;cout**3。PRIM算法求最经济的架设方法***endl;cout**4。KRUSCAL算法最经济的架设方法**endl;cout**********************************endlendl;ints;chary='y';while(y='y'){cout请选择菜单：endl;cins;switch(s){case1:cout用邻接矩阵存储为：endl;ljjzprint(G);break;case2:cout用邻接表存储为：endl;adjprint(gra);break;case3:for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j)g[i+1][j+1]=G.arcs[i][j].adj;coutPRIM算法最经济的架设方法为:endl;prim(g,d);break;case4:coutkruscal算法最经济的架设方法为:endl;kruscal_arc(G,gra);break;}coutendl是否继续？y/n:;ciny;if(y=='n')break;}}邻接表的输出：voidadjprint(algraphgra)//输出邻接表{inti;for(i=0;i!=gra.vexnum;++i){arcnode*p;couti;p=gra.vertices[i].firstarc;while(p!=NULL){coutp-adjvex;p=p-nextarc;}coutendl;}}邻接矩阵的输出：voidljjzprint(MGraph_LG)//输出邻接矩阵{inti,j;for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j)if(G.arcs[i][j].adj==10000){cout0;}else{coutG.arcs[i][j].adj;}coutendl;}}创建图并以邻接矩阵表示：intcreatMGraph_L(MGraph_L&G)//创建图用邻接矩阵表示{charv1,v2;inti,j,w;cout请输入城市数（顶点个数）和总道路的个数（弧的个数）:endl;cinG.vexnumG.arcnum;for(i=0;i!=G.vexnum;++i){cout输入城市名i+1endl;cinG.vexs[i];}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j){G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}for(intk=0;k!=G.arcnum;++k){cout请输入两城市间的距离（权）:endl;cinv1v2w;//输入一条边依附的两点及权值i=localvex(G,v1);//确定顶点V1和V2在图中的位置j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}cout**********************************endl;cout图创建成功endl;cout请根据如下进行操作endl;returnG.vexnum;}最小生成树kruscal算法：voidkruscal_arc(MGraph_LG,algraphgra)//最小生成树kruscal算法{edgedgs[20];inti,j,k=0;for(i=0;i!=G.vexnum;++i)for(j=i;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=G.arcs[i][j].adj;++k;}}intx,y,m,n;intbuf,edf;for(i=0;i!=gra.arcnum;++i)acrvisited[i]=0;for(j=0;j!=G.arcnum;++j){m=10000;for(i=0;i!=G.arcnum;++i){if(edgs[i].weightm){m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}buf=find(acrvisited,x);edf=find(acrvisited,y);edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout(x,y)m;coutendl;}}}返回V的位置：intlocalvex(MGraph_LG,charv)//返回V的位置{inti=0;while(G.vexs[i]!=v){++i;}returni;}最小生成树PRIM算法：intprim(intg[][max],intn)//最小生成树PRIM算法{intlowcost[max],prevex[max];//LOWCOST[]存储当前集合U分别到剩余结点的最短路径//prevex[]存储最短路径在U中的结点inti,j,k,min;for(i=2;i=n;i++)//n个顶点，n-1条边{lowcost[i]=g[1][i];//初始化prevex[i]=1;//顶点未加入到最小生成树中}lowcost[1]=0;//标志顶点1加入U集合for(i=2;i=n;i++)//形成n-1条边的生成树{min=inf;k=0;for(j=2;j=n;j++)//寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf((%d,%d)%d\t,prevex[k]-1,k-1,min);lowcost[k]=0;//顶点k加入Ufor(j=2;j=n;j++)//修改由顶点k到其他顶点边的权值if(g[k][j]lowcost[j]){lowcost[j]=g[k][j];prevex[j]=k;}printf(\n);}return0;}intacrvisited[100];//kruscal弧标记数组intfind(intacrvisited[],intf){while(acrvisited[f]0)f=acrvisited[f];returnf;}intfind(intacrvisited[],intf){while(acrvisited[f]0)f=acrvisited[f];returnf;}3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。Main()函数:Adjprint（）函数：ljjzprint()函数：开始creatMGraph_L()creatadj()Switch（）ljjzprint()adjprint()prim()kruscal_arc()结束开始Intii!=gra.vexnum输出ip!=NULLp-adjvexp=p-nextarc结束creatMGraph_L（）函数：creatadj()函数：开始inti,ji!=G.vexnumj!=G.vexnum输出G.arcs[i][j].adj结束开始输入顶点和弧的个数输入顶点输入权确定顶点在图中的位置结束prim()函数：开始生成表i=vexnum?建立邻接表设置表头结点为空循环生成其他结点，直到输入的邻接点为零生成空的表头结点做vexnum次循环生成其他结点，直道遇到空指针为止结束kruscal_arc()函数：开始标志顶点1加入U集合寻找满足边的一个顶点在U,另一个顶点在V的最小边形成n-1条边的生成树顶点k加入U修改由顶点k到其他顶点边的权值结束得到最小生成树开始确定弧的结点，以及弧的权比较弧的权的大小并对权小的赋值确定结点的位置结束不能生成环？localvex()函数：4.画出函数之间的调用关系图。四、调试分析1.实际完成的情况说明程序完成了用prim和kruscal求一个图的最小生成树，并对图以邻接表与邻接矩阵的形式进行存储2.程序的性能分析本程序操作简单，方便，能较好较快的完成最小