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

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

《数据结构课程设计最小生成树.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计最小生成树.docx（16页珍藏版）》请在冰点文库上搜索。

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

数据结构

课程设计报告

设计题目：

最小生成树

专业：

xxxxxx

院系：

计算机学院

姓名：

xxxxxxxxx

学号：

xxxxxx

时间：

2013年10月7日

一、设计目的……………………………………………………………….-2-

二、算法思想分析………………………………………………………-2-

1.算法思想………………………………………………………………..-3-

1）普里姆（Prim）算法思想……………………………………………………….-3-

2）克鲁斯卡尔（Kruskal）算法思想..........................................-3-

2.系统采用的数据结构和算法………………………………-3-

三、算法的描述与实现……………………………………………….-4-

四、用户手册………………………………………………………………-7-

五、总结…………………………………………………………………….-10-

六、参考文献…………………………………………………………….-10-

七、附录（源代码）………………………………………………...-10-

[摘要]选择一颗生成树，使之总的消费最少，也就是要构造连通网的最小代价生成树（简称为最小生成树）的问题，一颗生成树的代价就是树上各边的代价之和，构造最小生成树可以有多种算法，其中多数算法利用了MST的性质。

关键词：

最小生成树连通图普里姆算法克鲁斯卡尔算法MST

一、设计目的

1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

二、算法思想分析

该设计的要求是在n个城市之间建设网络，不仅要保证连通，还要求是最经济的架设方法。

根据克鲁斯卡尔和普里姆算法的不同之处，该程序将城市个数大于十个时应用普里姆算法求最小生成树，而城市个数小于十个时则应用克鲁斯卡尔进行计算。

1.算法思想

1）普里姆（Prim）算法思想

a）选择从0节点开始，并选择0节点相关联的最小权值边，将与这条边相关联的另一顶点出列；

b）在出列的节点中相关联的所有边中选择一条不与另一个已出列的节点相关联的权值最小的边，并将该边相关联的节点出列；

c）重复b）直到所有的节点出列。

2）克鲁斯卡尔（Kruskal）算法思想

为了使生成树上总的权值之和最小，应该使每一条边上的权值尽可能的小，所以应从权值最小的边选起，直至选出n-1条不能构成回路的权值最小的边位置。

具体做法如下：

首先构造一个含n个顶点的森林，然后按权值从小到大从连通图中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通图的最小生成树。

由于生成树上不允许有回路，因此并非每一条居当前最小的边都可选。

从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通，由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。

2.系统采用的数据结构和算法

1）数据结构

TypedefintVertextype;

Typedefintadimatrix[MaxVertexNum][MaxVertexNum];

TypedefintVertextypevexlist[MaxVertexNum];

TypedefintVexType;

TypedefintAdjType;

TypedefstructedgeElemedgeset[MaxVertexNum];

structedgeElem

{intfromvex;//头顶点

intendvex;//尾顶点

intweight;//权

};

Typedefstruct

{intn;//图的顶点个数

AdjTypeacrs[MAXVEX][MAXVEX];//边信息

}GraphMatrix;

Typedefstruct

{intstart_vex,stop_vex;//边的起点和终点

AdjTypeweight;//边的权

}Edge;

Edgemst[5];

2）算法

Great_adjmatrix（）;

Great_adjmatrix2（）;

Kruskal（）;

out_edgeaet（）;

prim（）;

三、算法的描述与实现

1.Great_adjmatrix（）和Great_adjmatrix2（）是两种建立图的方法；

2.克鲁斯卡尔算法（Kruskal）：

Voidkruskal（GraphMatrix*pgraph,Edgemst[]）

{inti,j,min,vx,vy;

intweight,minweight;

Edgeedge;

for（i=0;in-1;i++）

{mst[i].start_vex=0;

Mst[i].stop_vex=i+1;

Mst[i].weight=pgraph->arcs[0][i+1];

}

for（i=0;in-1;i++）//共n-1条边

{minweight=MAX;

min=i;

for（j=i;jn-1;j++）

//从所有（vx,vy）（vx∈U,vy∈V-U）中选出最短的边

if（mst[j].weight

{minweight=mst[j].weight;

min=j;

}

//mst[min]是最短的边（vx,vy）（vx∈U,vy∈V-U）,将mst[min]加入最小生成树

edge=mst[min];

mst[min]=mst[i];

mst[i]=edge;

vx=mst[i].stop_vex;//vx为刚加入最小生成树的顶点的下标

for（j=i+1;jn-1;j++）

{vy=mst[j].stop_vex;weight=pgraph->arcs[vx][vy];

if（weight

{mst[j].weight=weight;

mst[j].start_vex=vx;

}

}

}

}

3.普里姆算法（Prim）：

voidprim（adjmatrixGA,edgesetMST,intn）

//利用prim算法从0点出发求图的最小生成树

｛inti,j,t,k,w,min,m;

structedgeElemx;

for（i=0;i

if（i>0）//从0点连接其余顶点

｛MST[i-1].fromvex=0;

MST[i-1].endvex=i;

MST[i-1].weight=GA[0][i];

}

for（k=1;k

{min=MaxValue;

m=k-1;

for（j=k-1;j

if（MST[j].weight

{min=MST[j].weight;

M=j;

}//选择从0点出发权值最小的边

x=MST[k-1];MST[k-1]=MST[m];MST[m]=x;//交换位置

j=MST[k-1].endvex;//定位于权值最小边的尾顶点

for（i=k;i

{t=MST[i].endvex;

w=GA[j][t];

if（w

{MST[i].weight=w;

MST[i].fromvex=j;

}

}

}

}

4.out_edgeset（）功能为显示最小生成树。

四、用户手册

1.运行程序，得到如下窗口：

2.输入顶点数，选择算法：

1）当输入的顶点数小于10时，选择Kruskal算法，如下图

2）当输入的顶点数大于10时，选择Prim算法，如下图

五、总结

该程序实现了在n个城市之间建设网络，既保证了连通性，也成为了最经济的架设方法。

程序中应用了普里姆算法和克鲁斯卡尔算法，实现了矩阵的输出以及最小生成树的输出。

不过，该程序仍有不足之处，图的输入数据过大，易出错，不易返回，仍需完善。

六、参考文献

[1]《数据结构程序设计题典》李春葆编清华大学出版社

[2]《数据结构（C语言版）》严蔚敏吴伟民编清华大学出版社

[3]《数据结构课程设计》苏仕华编机械工业出版社

七、附录：

（源代码）

#include

#include

#defineMaxVertexNum12

#defineMaxEdgeNum20

#defineMaxValue1000

#defineMAXVEX6

#defineMAX1e+8

typedefintVertextype;

typedefintadjmatrix[MaxVertexNum][MaxVertexNum];

typedefVertextypevexlist[MaxVertexNum];

typedefintVexType;

typedefintAdjType;

typedefstructedgeElemedgeset[MaxVertexNum];

structedgeElem

{intfromvex;//头顶点

intendvex;//尾顶点

intweight;//权

};

typedefstruct{

intn;/*图的顶点个数*/

/*VexTypevexs[MAXVEX];顶点信息*/

AdjTypearcs[MAXVEX][MAXVEX];/*边信息*/

}GraphMatrix;

typedefstruct{

intstart_vex,stop_vex;/*边的起点和终点*/

AdjTypeweight;/*边的权*/

}Edge;Edgemst[5];

voidCreat_adjmatrix（vexlistGV,adjmatrixGA,intn,inte）

{inti,j,k,w;

printf（"输入%d个顶点序号（0--n-1）：

",n）;

for（i=0;i

scanf（"%d",&GV[i]）;//读入顶点信息

for（i=0;i

for（j=0;j

if（i==j）GA[i][j]=0;

elseGA[i][j]=MaxValue;

printf（"输入%d条无向带权边（序号序号权值）：

\n",e）;

for（k=0;k

{scanf（"%d%d%d",&i,&j,&w）;

GA[i][j]=GA[j][i]=w;//对称

}

}

voidCreat_adjmatrix2（vexlistGV,adjmatrixGA,intm,inte,GraphMatrix&graph）

{inti,j,k,w,x,y;

printf（"输入%d个顶点序号（0-m-1），序号从0开始。

",m）;

for（i=0;i

{scanf（"%d",&GV[i]）;//读入顶点信息

if（GV[i]>=m）

{printf（"您输入的序号有误，请输入0到%d-1之间的数，请重新输入。

\n",m）;

scanf（"%d",&GV[i]）;}

}

for（i=0;i

for（j=0;j

GA[i][j]=MaxValue;

printf（"请输入有多少条边。

\n"）;

scanf（"%d",&e）;

printf（"输入%d条无向带权边（序号序号权值）：

\n",e）;

for（k=0;k

{scanf（"%d%d%d",&i,&j,&w）;

GA[i][j]=GA[j][i]=w;//对称

}

printf（"您输入的图的存贮为下面表，如果不可达则用1000表示。

\n"）;

graph.n=m;

for（x=0;x

{for（y=0;y

graph.arcs[x][y]=GA[x][y];

printf（"%-4d",graph.arcs[x][y]）;}

printf（"\n"）;

}

}

voidkruskal（GraphMatrix*pgraph,Edgemst[]）{

inti,j,min,vx,vy;

intweight,minweight;Edgeedge;

for（i=0;in-1;i++）{

mst[i].start_vex=0;

mst[i].stop_vex=i+1;

mst[i].weight=pgraph->arcs[0][i+1];

}

for（i=0;in-1;i++）{/*共n-1条边*/

minweight=MAX;min=i;

XX文库-让每个人平等地提升自我for（j=i;jn-1;j++）/*从所有边（vx,vy）（vx∈U,vy∈V-U）中选出最短的边*/

if（mst[j].weight

minweight=mst[j].weight;

min=j;

}

/*mst[min]是最短的边（vx,vy）（vx∈U,vy∈V-U），将mst[min]加入最小生成树*/

edge=mst[min];

mst[min]=mst[i];

mst[i]=edge;

vx=mst[i].stop_vex;/*vx为刚加入最小生成树的顶点的下标*/

for（j=i+1;jn-1;j++）{/*调整mst[i+1]到mst[n-1]*/

vy=mst[j].stop_vex;weight=pgraph->arcs[vx][vy];

if（weight

mst[j].weight=weight;

mst[j].start_vex=vx;

}

}

}

}

voidout_edgeset（edgesetMST,inte）//显示最小生成树

{intk;

printf（"最小的消耗路线为\n"）;

for（k=0;k

printf（"（%d%d%d）\n",MST[k].fromvex,MST[k].endvex,MST[k].weight）;

}

voidprim（adjmatrixGA,edgesetMST,intn）//利用prim算法从0点出发求图的最小生成树

{inti,j,t,k,w,min,m;

structedgeElemx;

for（i=0;i

if（i>0）//从0点连接其余顶点

{MST[i-1].fromvex=0;

MST[i-1].endvex=i;

MST[i-1].weight=GA[0][i];

}

for（k=1;k

{min=MaxValue;

m=k-1;

for（j=k-1;j

if（MST[j].weight

x=MST[k-1];MST[k-1]=MST[m];MST[m]=x;//交换位置

j=MST[k-1].endvex;//定位于权值最小边的尾顶点

for（i=k;i

{t=MST[i].endvex;w=GA[j][t];

if（w

{MST[i].weight=w;

MST[i].fromvex=j;

}

}

}

}

voidmain（）

{

intn,e,i;

inta;

system（"color71"）;//改变屏幕颜色

printf（"┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"）;

printf（"┃㊣必做题：

最小生成树㊣┃\n"）;

printf（"┃姓名：

xxxx┃\n"）;

printf（"┃学号：

xxxxxxxxx┃\n"）;

printf（"┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"）;

vexlistGV;//顶点表

adjmatrixGA;//边表

edgesetMST;//最小生成树

do{

printf（"输入图的顶点数n，我们将根据您输入的数据大小选择合适的算法。

\n"）;

scanf（"%d",&n）;

if（n>=10）//大于10用prim算法来实现，否则kruskal算法来实现

{

printf（"用prim算法从0点出发求图的最小生成树为：

\n"）;

printf（"请输入图的边数。

\n"）;

canf（"%d",&e）;

Creat_adjmatrix（GV,GA,n,e）;//创建图

prim（GA,MST,n）;//生成最小生成树

out_edgeset（MST,n-1）;//输出最小生成树

}

else{

printf（"用kcuskal算法的最小生成树为：

\n"）;

GraphMatrixgraph;//定义一个结构体来表示存储结构

Creat_adjmatrix2（GV,GA,n,e,graph）;//创建图

kruskal（&graph,mst）;//生成最小生成树

rintf（"最小的消耗路线为\n"）;

for（i=0;i

printf（"（%d%d%d）\n",mst[i].start_vex,

mst[i].stop_vex,mst[i].weight）;//输出最小生成树

}

printf（"谢谢使用！

\n"）;

printf（"继续？

输入1继续，输入0退出。

\n"）;//方便用户重复使用

scanf（"%d",&a）;

getchar（）;

system（"cls"）;//清屏语句

}while（a==1）;

}