最小生成树问题知识讲解.docx

最小生成树问题知识讲解.docx

《最小生成树问题知识讲解.docx》由会员分享，可在线阅读，更多相关《最小生成树问题知识讲解.docx（18页珍藏版）》请在冰点文库上搜索。

最小生成树问题知识讲解

最小生成树问题

榆林学院12届课程设计

《最小生成树问题》

课程设计说明书

学生姓名：

赵佳

学号：

1412210112

院系：

信息工程学院

专业：

计算机科学与技术

班级：

计14本1

指导教师：

答辩时间：

年月日

最小生成树问题

一、问题陈述

最小生成树问题

设计要求：

在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

存储结构采用多种。

求解算法多种。

二、需求分析

1.在n个城市之间建设网络，只需保证连通即可。

2.求城市之间最经济的架设方法。

3.采用多种存储结构，求解算法也采用多种。

三、概要设计

1、功能模块图

开始

创建一个图

功能选择

1.建立邻接矩阵

2.建立邻接表

3.kruskal算法

4.PRIM算法

结束

2、功能描述

（1）CreateUDG（）

创建一个图：

通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。

（2）Switch（）

功能选择：

给用户提示信息，让用户选择相应功能。

（3）Adjacency_Matrix（）

建立邻接矩阵：

将用户输入的数据整理成邻接矩阵并显现在屏幕上。

（4）Adjacency_List（）

建立邻接表：

将用户输入的数据整理成临接表并显现在屏幕上。

（5）MiniSpanTree_KRSL（）

kruskal算法：

利用kruskal算法求出图的最小生成树，即：

城市之间最经济的连接方案。

（6）MiniSpanTree_PRIM（）

PRIM算法：

利用PRIM算法求出图的最小生成树，即：

城市之间最经济的连接方案。

四、详细设计

本次课程设计采用两种存储结构以及两种求解算法。

1、两种存储结构的存储定义如下：

typedefstructArcell

{

doubleadj;

}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedefstruct

{

charvexs[MAX_VERTEX_NUM];//节点数组

AdjMatrixarcs;//邻接矩阵

intvexnum,arcnum;//图的当前节点数和弧数

}MGraph;

typedefstructPnode//用于普利姆算法

{charadjvex;//节点

doublelowcost;//权值

}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义

typedefstructKnode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点

{

charch1;//节点1

charch2;//节点2

doublevalue;//权值

}Knode,Dgevalue[MAX_VERTEX_NUM];

2、求解算法采用Prim算法和Kruskal算法。

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

普里姆算法（Prim）算法是一种构造性算法，生成最小生成树的步骤如下：

初始化U={v}。

以v到其他顶点的所有边为候选边。

重复一下步骤（n-1）次，使得其他（n-1）个顶点被加入到U中。

从候选边中挑选权值最小的边加入TE，设该边在V—U中的顶点是vk，将顶点vk加入到U中;

考察当前V—U中的所有顶点vj，修改候选边：

若（vk,vj）的权值小于原来和vj关联的候选边，则用（vk,vj）取代后者作为候选边。

开始

标志顶点1加入U集合

寻找满足边的一个顶点在U,另一个顶点在V的最小边

形成n-1条边的生成树

顶点k加入U

修改由顶点k到其他顶点边的权值

结束

得到最小生成树

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

克鲁斯卡尔（Kruskal）算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

假设G=（V,E）是一个具有n个顶点的带权连通无向图，T=（U,TE）是G的最小生成树，则构造最小生成树的步骤如下：

置U的初值等于V（即包含有G中的全部顶点），TE的初值为空集（即图T中每一个顶点都构成一个分量）。

将图G中的边按权值从小到大的顺序依次选取：

若选取的边未使生成树T形成回路，则加入TE，否则舍弃，直到TE中包含（n-1）条边为止。

3、使用的函数

intCreateUDG（MGraph&G,Dgevalue&dgevalue）;

intLocateVex（MGraphG,charch）;

intMinimum（MGraphG,Closedgeclosedge）;

voidMiniSpanTree_PRIM（MGraphG,charu）;

voidSortdge（Dgevalue&dgevalue,MGraphG）;

voidAdjacency_Matrix（MGraphG）;

voidAdjacency_List（MGraphG,Dgevaluedgevalue）;

函数之间的调用关系图：

CreateUDG（）

main（）

Adjacency_Matrix（）

Adjacency_List（）

MiniSpanTree_KRSL（）

MiniSpanTree_PRIM（）

locateVex（）

locateVex（）

Minimum（）

locateVex（）

Sortdge（）

五、程序代码

#include

#include

#include

#defineMAX_VERTEX_NUM20

#defineOK1

#defineERROR0

#defineMAX1000

typedefstructArcell

{

doubleadj;

}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedefstruct

{

charvexs[MAX_VERTEX_NUM];//节点数组

AdjMatrixarcs;//邻接矩阵

intvexnum,arcnum;//图的当前节点数和弧数

}MGraph;

typedefstructPnode//用于普利姆算法

{

charadjvex;//节点

doublelowcost;//权值

}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义

typedefstructKnode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点

{

charch1;//节点1

charch2;//节点2

doublevalue;//权值

}Knode,Dgevalue[MAX_VERTEX_NUM];

intCreateUDG（MGraph&G,Dgevalue&dgevalue）;

intLocateVex（MGraphG,charch）;

intMinimum（MGraphG,Closedgeclosedge）;

voidMiniSpanTree_PRIM（MGraphG,charu）;

voidSortdge（Dgevalue&dgevalue,MGraphG）;

voidAdjacency_Matrix（MGraphG）;

voidAdjacency_List（MGraphG,Dgevaluedgevalue）;

intCreateUDG（MGraph&G,Dgevalue&dgevalue）//构造无向加权图的邻接矩阵

{

inti,j,k;

cout<<"请输入城市个数及其之间的可连接线路数目：

";

cin>>G.vexnum>>G.arcnum;

cout<<"请输入各个城市名称（分别用一个字符代替）：

";

for（i=0;i

cin>>G.vexs[i];

for（i=0;i

for（j=0;j

{

G.arcs[i][j].adj=MAX;

}

cout<<"请输入两个城市名称及其连接费用（严禁连接重复输入!

）：

"<

for（k=0;k

{

cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;

i=LocateVex（G,dgevalue[k].ch1）;

j=LocateVex（G,dgevalue[k].ch2）;

G.arcs[i][j].adj=dgevalue[k].value;

G.arcs[j][i].adj=G.arcs[i][j].adj;

}

returnOK;

}

intLocateVex（MGraphG,charch）//确定节点ch在图G.vexs中的位置

{

inta;

for（inti=0;i

if（G.vexs[i]==ch）

a=i;

returna;

}

voidAdjacency_Matrix（MGraphG）//用邻接矩阵存储数据

{

inti,j;

for（i=0;i

{

for（j=0;j

if（G.arcs[i][j].adj==MAX）

cout<<0<<"";

else

cout<

cout<

}

}

voidAdjacency_List（MGraphG,Dgevaluedgevalue）//用邻接表储存数据

{

inti,j;

for（i=0;i

{

cout<";

for（j=0;j

if（dgevalue[j].ch1==G.vexs[i]&&dgevalue[j].ch2!

=G.vexs[i]）

cout<";

elseif（dgevalue[j].ch1!

=G.vexs[i]&&dgevalue[j].ch2==G.vexs[i]）

cout<";

cout<<"\b\b"<

}

}

voidMiniSpanTree_KRSL（MGraphG,Dgevalue&dgevalue）//克鲁斯卡尔算法求最小生成树

{

intp1,p2,i,j;

intbj[MAX_VERTEX_NUM];//标记数组

for（i=0;i

bj[i]=i;

Sortdge（dgevalue,G）;//将所有权值按从小到大排序

for（i=0;i

{

p1=bj[LocateVex（G,dgevalue[i].ch1）];

p2=bj[LocateVex（G,dgevalue[i].ch2）];

if（p1!

=p2）

{

cout<<"城市"<

"<

for（j=0;j

{

if（bj[j]==p2）

bj[j]=p1;

}

}

}

}

voidSortdge（Dgevalue&dgevalue,MGraphG）//对dgevalue中各元素按权值按从小到大排序

{

inti,j;

doubletemp;

charch1,ch2;

for（i=0;i

{

for（j=i;j

{

if（dgevalue[i].value>dgevalue[j].value）

{

temp=dgevalue[i].value;

dgevalue[i].value=dgevalue[j].value;

dgevalue[j].value=temp;

ch1=dgevalue[i].ch1;

dgevalue[i].ch1=dgevalue[j].ch1;

dgevalue[j].ch1=ch1;

ch2=dgevalue[i].ch2;

dgevalue[i].ch2=dgevalue[j].ch2;

dgevalue[j].ch2=ch2;

}

}

}

}

voidMiniSpanTree_PRIM（MGraphG,charu）//普里姆算法求最小生成树

{

inti,j,k;

Closedgeclosedge;

k=LocateVex（G,u）;

for（j=0;j

{

if（j!

=k）

{

closedge[j].adjvex=u;

closedge[j].lowcost=G.arcs[k][j].adj;

}

}

closedge[k].lowcost=0;

for（i=1;i

{

k=Minimum（G,closedge）;

cout<<"城市"<

"<

closedge[k].lowcost=0;

for（j=0;j

{

if（G.arcs[k][j].adj

{

closedge[j].adjvex=G.vexs[k];

closedge[j].lowcost=G.arcs[k][j].adj;

}

}

}

}

intMinimum（MGraphG,Closedgeclosedge）//求closedge中权值最小的边，并返回其顶点在vexs中的位置

{

inti,j;

doublek=1000;

for（i=0;i

{

if（closedge[i].lowcost!

=0&&closedge[i].lowcost

{

k=closedge[i].lowcost;

j=i;

}

}

returnj;

}

voidmain（）

{

MGraphG;

Dgevaluedgevalue;

CreateUDG（G,dgevalue）;

charu;

cout<<"图创建成功。

";

cout<<"请根据如下菜单选择操作。

\n";

cout<<"1、用邻接矩阵存储：

"<

cout<<"2、用邻接表存储：

"<

cout<<"3、克鲁斯卡尔算法求最经济的连接方案"<

cout<<"4、普里姆算法求最经济的连接方案"<

ints;

chary='y';

while（y='y'）

{

cout<<"请选择菜单：

"<

cin>>s;

switch（s）

{

case1:

cout<<"用邻接矩阵存储为：

"<

Adjacency_Matrix（G）;

break;

case2:

cout<<"用邻接表存储为：

"<

Adjacency_List（G,dgevalue）;

break;

case3:

cout<<"克鲁斯卡尔算法最经济的连接方案为:

"<

MiniSpanTree_KRSL（G,dgevalue）;

break;

case4:

cout<<"普里姆算法最经济的连接方案为:

"<

cout<<"请输入起始城市名称：

";

cin>>u;

MiniSpanTree_PRIM（G,u）;

break;

default:

cout<<"输入有误!

";

break;

}

cout<

y/n:

";

cin>>y;

if（y=='n'）

break;

}

}

六、运行结果与测试

七、设计体会与总结

通过本次课程设计，我在程序设计中，用邻接矩阵和邻接表这两种存储结构进行编程，且对Prim算法和Kruskal算法生成最小生成树有了一个初步的了解，同时也为日后的毕业设计打下了良好的基础。

而且通过课程设计在下述各方面得到了锻炼：

1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。

2、提高程序设计和调试能力。

通过上机实习，验证自己设计的算法的正确性。

学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

3、培养算法分析能力。

分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。

在本次课程设计中，知道如何在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

并且用了多种求解方式。

这几天的课程设计让我充分地体会到了上机实践对于计算机编程的重要性。

只顾学习理论是远远不够的。

实践中可以发现许许多多的问题，然后通过同学老师的帮助，得以解决，让自己的编程能力得到极大的提升。