最小生成树课程设计

一目的与内容 2二、数据构造设计 2三、核心算法 4四、运行结果 8五、调试与心得体会 91目的：本课程设计的目的是了解并把握数据构造与算法的设计方法，具备初步的独立分练用系统的观点和软件开发一般标准进展软件开发。内容：利用普里姆算法和克鲁斯卡尔算法求网的最小生成树按挨次输诞生成树中各条边以及它们的权值二、数据构造设计(ADT)如下：ADTGraph{ 数据对象V：v是具有一样特性的数据元素的集合，称为顶点集。R：R={VR}VR={<v,w>|v,w属于v且p(v,w),(v,w)v到wp(v,w)根本操作：CreatGraph(&G,V,VR)；初始条件：V是图的顶点集，VR是图中弧的集合。VVRG。LocateVex(G,u)；G存在,uG中顶点有一样的特征。信息。DestoryGraph(&u)；操作结果：销毁图G。GetVex(G,v)；v的值。NextAdjVex(G,v,w)；G存在，v是图中某个顶点，wv的邻接顶点。操作结果：返回v的〔相对于w的〕下一个邻接顶点。假设wv的最终一个邻接点，则返回“空”。BFSTraverse(G,Visit())；初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进展广度优先遍历。在遍历过程中对每个顶点调用函数Visitvisit()失败，则操作失败。}存储构造Typedefstruct{int adj;int weight;}AdjMatrix[MAX][MAX];Typedef struct{djMatrix arc;intvexnum,arcnum;}MGraph;开始功能选择开始功能选择结束1、建2、用3、用立邻primkruska接矩算法l算法阵求解最最三、核心算法kruskal算法及代价模块代码，五段代码块分别有着不同的作用，共同满足了课题所需要实现的功能。主函数模块代码algraphgra; MGraph_LG; inti,d,g[20][20];chara=”a”; d=creatMGraph_L(G); vnodev;cout<<endl<<“留意：假设该图为非强连通图(含有多个连通重量)时“<<endl<<“最小生成树不存在,则显示为非法值“<<endl<<endl;cout<<“… 菜单 “<<endl<<endlcout<<“0、显示该图的邻接矩阵 “<<endl、最小生成树PRIM算法及代价 “<<endlints; chary=”y”;while(y=”y”) {cout<<“请选择菜单：“<<endl; switch(s){case0: cout<<“邻接矩阵显示如下：“<<endl; ljjzprint(G); case1: for(i=0;i!=G.vexnum;++i)for(intj=0;j!=G.vexnum;++j) g[i+1][j+1]=G.arcs[i][j].adj;cout<<“prim:“<<endl; prim(g,d); break; }cout<<endl<<“是否连续？y/n:“; cin>>y; if(y==”n”) break; }creatMGraphyN确定是否连续。邻接矩阵定义模块代码typedefstructArcCell{intadj; char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20]; AdjMatrixarcs;intvexnum,arcnum;}MGraph_L;intlocalvex(MGraph_LG,charv){ inti=0; while(G.vexs[i]!=v) {++i;} returni;}20。创立链接矩阵模块代码intcreatMGraph_L(MGraph_L&G){ charv1,v2; inti,j,w;创立无向图〔城市分布图〕…………“<<endl;cout请输入G顶点〔城市〕和弧〔边〕的个数:(46)不包括“”“<<endl;for(i=0;i!=G.vexnum;++i){ 输入顶点〔城市〕“<<i<<endl;for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j)

cin>>G.vexs[i]; }{ G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; }for(intk=0;k!=G.arcnum;++k){ cout<<“输入一条边依附的顶点〔城市〕和权〔距离〕 :(ab3)不包括“”“<<endin>>v1>>v2>>w;i=localvex(G,v1); j=localvex(G,v2);G.arcs[i][j].adj=w; G.arcs[j][i].adj=w;}cout<<“图G邻接矩阵创立成功！“<<endl; returnG.vexnum;}creatMGraph_L〔〕创立连接矩阵。Prim算法及代价模块代码intprim(intg[][max],intn){intlowcost[max],prevex[max];inti,j,k,min;intsum=o;for(i=2;i<=n;i++){lowcost[i]=g[1][i]; prevex[i]=1; }lowcost[1]=0; for(i=2;i<=n;i++) { min=inf; k=0;for(j=2;j<=n;j++)if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j; printf(“(%d,%d)%d\t“,prevex[k]-1,k-1,min);sum+=min; lowcost[k]=0;for(j=2;j<=n;j++) if(g[k][j]<lowcost[j]){ lowcost[j]=g[k][j]; prevex[j]=k; printf(“\n“);}cout<<“最少生成树的代价:“; cout<<sum; return0;}边权值的比较，最终调用prim函数，实现最小生成树的生成，同时运用sum把最小生成树各边权值相加得到最小生成树的代价。最小生成树kruskal算法及代价模块代码voidMiniSpanTree(MGraphA*D)//生成最小生成树{ inti,j,n, m,SUM=0; intk=1;intparent[M];edgeedges[M];for(i=1;i<D->vexnum;i++){ for(j=i+1;j<=D->vexnum;j++){ if(D->arc[i][j].adj==1){ edges[k].begin=i; edges[k].end=j;edges[k].weight=D->arc[i][j].weight; }}sort(edges,D);for(i=1;i<=D->arcnum;i++){ parent[i]=0; }最小生成树为:\n“);for(i=1;i<=D->arcnum;i++)//核心局部{ n=Find(parent,edges[i].begin); m=Find(parent,edges[i].end);if(n!=m){ parent[n]=m;printf(“<<%d,%d>> %d\n“,edges[i].begin,edges[i].end,edges[i].weight);SUM=SUM+edges[i].weight;}}cout<<“最少生成树的代价:“; cout<<SUM.sum把最小生成树各边权值相加得到最小生成树的代价。}四、运行结果将程序员录入后,让其运行。将会消灭一个菜单的界面，执行各种操作均有其对应的操作简洁便利有用，下面即为一些操作的示意图。1所示。图1 初界面1-3三个选项，可选取其中的一个选项进展操作。12所示。图2 建立邻接矩阵符号及与各个顶点相关联的弧与权值，存在邻接矩阵中。34所示。图3 求的最小生成树图中显示了求得的最小生成树所对应的边、权值与最小生成树的代价。7五、调试分析与体会c语言不是很了解，有时无视了一些关键的细节，使得在编写程序的过程中消灭了一些问题。对于打字有时马虎课程设计完满完工。1、问题一：求出图中的最小值现象：求出的最小值是0。缘由