最小生成树课程设计.docx

该【最小生成树课程设计 】是由【ATONGMU】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【最小生成树课程设计 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。目录
一、目的与内容 2
二、数据构造设计 2
三、核心算法 4
四、运行结果 8
五、调试与心得体会 9
1
一、目的与内容目的:
本课程设计的目的是了解并把握数据构造与算法的设计方法,具备初步的独立分析和设计力量;初步把握软件开发过程的问题分析、系统设计、程序编码、测试等根本方法和技能;提高综合运用所学的理论学问和方法独立分析和解决问题的力量;训练用系统的观点和软件开发一般标准进展软件开发。
内容:
建立一个图,其存储方式可以承受邻接矩阵形式,需要定义两个数组,一个存储顶点,一个存储边,存储边的数组说明节点间的连通关系和边的权值;。
利用普里姆算法和克鲁斯卡尔算法求网的最小生成树
按挨次输诞生成树中各条边以及它们的权值
二、数据构造设计
抽象数据类型(ADT)如下:
ADTGraph
{ 数据对象V:v是具有一样特性的数据元素的集合,称为顶点集。数据关系R:R={VR}
VR={<v,w>|v,w属于v且p(v,w),(v,w)表示从v到w的弧,谓词p(v,w)
定义了弧<v,w>的意义或信息}
根本操作:
CreatGraph(&G,V,VR);
初始条件:V是图的顶点集,VR是图中弧的集合。操作结果:按V和VR的定义构造图G。
LocateVex(G,u);
初始条件:图G存在,u和G中顶点有一样的特征。
操作结果:假设G中存在顶点u,则返回该顶点在图中的位置;否则返回其他信息。
DestoryGraph(&u);
初始条件:图G存在。操作结果:销毁图G。
GetVex(G,v);
初始条件:图G存在,v是图中某个顶点。操作结果:返回v的值。
NextAdjVex(G,v,w);
初始条件:图G存在,v是图中某个顶点,w是v的邻接顶点。
操作结果:返回v的〔相对于w的〕下一个邻接顶点。假设w是v的最终一个邻接点,则返回“空”。
BFSTraverse(G,Visit());
初始条件:图G存在,Visit是顶点的应用函数。
操作结果:对图进展广度优先遍历。在遍历过程中对每个顶点调用函数Visit
一次且仅一次。一旦visit()失败,则操作失败。}
存储构造
Typedefstruct
{
int adj;
int weight;
}AdjMatrix[MAX][MAX];Typedef struct
{
djMatrix arc;
intvexnum,arcnum;
}MGraph;
开始
功能选择
结束
流程图
1、建
2、用
3、用
立邻
prim
kruska
接矩
算法
l算法
阵
求解
最最
1
三、核心算法
在该函数中主要有五段代码块,分别是主函数代码块、邻接矩阵定义模块代码、创立链接矩阵模块代码、最小生成树Prim算法及代价模块代码与最小生成树kruskal算法及代价模块代码,五段代码块分别有着不同的作用,共同满足了课题所需要实现的功能。
主函数模块代码
algraphgra; MGraph_LG; inti,d,g[20][20];chara=”a”; d=creatMGraph_L(G); vnodev;
cout<<endl<<“留意:假设该图为非强连通图(含有多个连通重量)时“<<endl
<<“最小生成树不存在,则显示为非法值“<<endl<<endl;
cout<<“… 菜单 “<<endl<<endl
cout<<“0、显示该图的邻接矩阵 “<<endl
cout<<“1、最小生成树PRIM算法及代价 “<<endl
ints; chary=”y”;
while(y=”y”) {cout<<“请选择菜单:“<<endl; cin>>s;switch(s){
case0: cout<<“邻接矩阵显示如下:“<<endl; ljjzprint(G); break;case1: for(i=0;i!=;++i)
for(intj=0;j!=;++j) g[i+1][j+1]=[i][j].adj;cout<<“prim:“<<endl; prim(g,d); break; }cout<<endl<<“是否连续?y/n:“; cin>>y; if(y==”n”) break; }
}
该主函数用一个循环语句,来执行其它的函数的功能。从键盘输入顶点数和边数上限,再调用定义连接矩阵的函数,后输出创立连接矩阵的信息,再调用creatMGraph
〔〕函数,接着进入菜单,然后再选择输入一个数确定是要输出连接矩阵还是最小生成树及代价,最终选择输入确定字母y或N确定是否连续。
1
邻接矩阵定义模块代码
typedefstructArcCell{
intadj; char*info;
}ArcCell,AdjMatrix[20][20];typedefstruct{
charvexs[20]; AdjMatrixarcs;intvexnum,arcnum;
}MGraph_L;
intlocalvex(MGraph_LG,charv)
{ inti=0; while([i]!=v) {++i;} returni;}
用typedefstruct定义连接矩阵,通过二维数组来存储连接矩阵,并设定参数的最大值为20。
创立链接矩阵模块代码
intcreatMGraph_L(MGraph_L&G)
{ charv1,v2; inti,j,w;
cout<<“…………创立无向图〔城市分布图〕…………“<<endl;cout<<“请输入图G顶点〔城市〕和弧〔边〕的个数:(46)不包括“”“<<endl;
cin>>>>;for(i=0;i!=;++i)
1
{ cout<<“输入顶点〔城市〕“<<i<<endl;
for(i=0;i!=;++i)for(j=0;j!=;++j)
cin>>[i]; }
1
{ [i][j].adj=int_max; [i][j].info=NULL; }
for(intk=0;k!=;++k)
{ cout<<“输入一条边依附的顶点〔城市〕和权〔距离〕 :(ab3)不包括
1
“”“<<endlc;in>>v1>>v2>>w;i=localvex(G,v1); j=localvex(G,v2);
[i][j].adj=w; [j][i].adj=w;}
cout<<“图G邻接矩阵创立成功!“<<endl; ;}
该语句是从键盘输入顶点数和边数,输入顶点和权值,通过循环语句的调用,最终调用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++) //形成n-1条边的生成树
{ 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)//生成最小生成树
1
{ 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; k++;}
}
}
sort(edges,D);
for(i=1;i<=D->arcnum;i++)
{ parent[i]=0; }printf(“最小生成树为:\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.
该语句运用一系列的循环语句来实现的,利用前面的创立好的链接矩阵,通过各边权值的比较,最终调用MiniSpanTree函数,实现最小生成树的生成,同时运用sum把最小生成树各边权值相加得到最小生成树的代价。
}
1
四、运行结果
将程序员录入后,让其运行。将会消灭一个菜单的界面,执行各种操作均有其对应的代码。要执行何种操作只需输入对应的指令即可进展,在每步操作后均会有相应的提示。操作简洁便利有用,下面即为一些操作的示意图。
运行程序后出界面,运行结果如图1所示。
图1 初界面
图中有1-3三个选项,可选取其中的一个选项进展操作。选取选项1进展操作,运行结果如图2所示。
图2 建立邻接矩阵
依据提示,分别输入无向图的顶点个数与弧的个数,然后依次输入各个顶点所对应的符号及与各个顶点相关联的弧与权值,存在邻接矩阵中。
假设选取选项3,运行结果如图4所示。
图3 求的最小生成树
图中显示了求得的最小生成树所对应的边、权值与最小生成树的代价。
7
五、调试分析与体会
在我组的集体努力下,课程设计最终完成,由于我们对数据构造和c语言不是很了解,有时无视了一些关键的细节,使得在编写程序的过程中消灭了一些问题。对于打字有时马虎导致消灭一些难以觉察的小错误,在我们的急躁,细致的调试下最终使得程序能够运行,课程设计完满完工。
1、问题一:求出图中的最小值现象:求出的最小值是0。
缘由:图中没有连通的两个顶点之间的权值赋值为0。
2、问题二:求最小生成树时,else语句需再调用一个函数。现象:对某些二叉树能求出最小生成树,但不能普遍适应。
缘由:对于找最小生成树边的各种可能没有考虑全面,代码才没有广泛的适应性。
3、问题三:两个顶点之间的边是否是最小生成树的边。现象:代码的功能不能区分出是否是最小生成树的边。
缘由:把简洁的代码写的很简单,从而杂乱无章消灭错误。
8