最小生成树prim算法.docx

最小生成树prim算法.docx

《最小生成树prim算法.docx》由会员分享，可在线阅读，更多相关《最小生成树prim算法.docx（19页珍藏版）》请在冰点文库上搜索。

最小生成树prim算法

《数据结构》

　　课程设计报告

（最小生成树问题）

1课程设计的目的和意义

2需求分析

3系统（项目）设计

4系统实现

5系统调试

附录源程序

1课程设计的目的和意义

据《数据结构》课堂讲授及书本内容，学生做相应的自主练习，消化课堂所讲解的内容；通过调试典型例题或习题积累调试C及C++程序的经验；通过完成课程设计中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力。

“数据结构”作为计算机专业基础课，该课程的目标就是使学生学会如何从问题出发，分析数据，构造求解问题的数据结构和算法，培养学生有一定进行较复杂程序设计的能力。

本次课程设计的内容是用最小生成树的构造来表示城市间的最小代价即最小距离，最小生成树可以用连接矩阵和连接表表示，而它们的区别就是连接矩阵一般用来表示密集型的网络，连接表一般用来表示稀疏型的网络，连接矩阵是用数组来存储，连接了是用链表来存储的，比较复杂密集型的网络就网连接矩阵较适用了，设计中运用了Prim算法，“构造可以使n个城市连接的最小生成树”问题就是用连接矩阵和Prim算法处理的一个实际应用。

通过这个题目的设计实例，了解了最小生成树的实际运用意义，也了解连接矩阵和连接表的相同与不同之处，进一步加深了对最小生成树结构和Prim算法的理解。

通过这次课程设计，一方面使学生加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空分析等课程基本内容的理解，另一方面，使学生在程序设计方法（如抽象数据类型、结构化分析、模块化设计和结构化设计）、C和C++语言编程环境以及程序的调试和测试方面受到比较系统的严格的训练。

2需求分析

1.题目：

最小生成树的Prime算法实现（难度**）

要求：

1）先任意创建一个图；

2）用Prime算法，求出该图的最小生成树

。

3系统（项目）设计

（包括总体设计和详细设计）

一.设计思想及方案：

n个顶点的连通图应该至少有n-1条边，而生成树正好有n-1条边，所以生成树是对应的连通图的极小连通子图。

带权的无向图，经过遍历得到的生成树也是带权的，最小生成树即权值最小的生成树。

所以要求图的最小生成树，即只要求权值最小的极小连通子图。

这实际上是求图的一个生成树。

同时还要考虑造价最低这个条件。

一棵树的权定义为它所含各边的权之和。

一个连通网络的最小生成树是该图所有生成树中权最小的生成树普里姆算法（Prim）算法：

设N=（V,{E}）是连通图，TE是N上最小生成树中边的集合，U为V中具有最小生成树的顶点集合，初始时，TN为空，U={uo}（uo∈V）,重复下叙操作：

在所有u∈U、v∈V-U的边（u,v）∈E中找一条代价最小的边（u0，v0）并入集合TE，同时v0并入集合TE,同时,直到U=V为止，此时TE必有n-1条边，且T=（V,{TE}）为N的最小生成树。

二．模块的设计及介绍

（1）.主程序模块

voidmain（）{

{

接受命令；

处理命令；

Cout<

y/n””;

}

}

（2）.创建链接矩阵模块

intcreatMGraph_L（参数）{

for{

接受命令；

处理命令；

}

cout<<"命令"<

}

4系统实现

各模块关键代码及算法的解释：

（1）.主函数模块代码

{

algraphgra;

MGraph_LG;

inti,d,g[20][20];

chara='a';

d=creatMGraph_L（G）;

vnodev;

cout<

若该图为非强连通图（含有多个连通分量）时"<

<<"最小生成树不存在,则显示为非法值"<

cout<<"…………………菜单……………………"<

cout<<"0、显示该图的邻接矩阵……………………"<

cout<<"1、最小生成树PRIM算法及代价…………………"<

ints;

chary='y';

while（y='y'）

{

cout<<"请选择菜单：

"<

cin>>s;

switch（s）

{

case0:

cout<<"邻接矩阵显示如下：

"<

ljjzprint（G）;

break;

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:

"<

prim（g,d）;

break;

}

cout<

y/n:

";

cin>>y;

if（y=='n'）

break;

}

}

程序解释：

该主函数用一个循环语句，来执行其它的函数的功能。

从键盘输入顶点数和边数上限，再调用定义连接矩阵的函数，后输出创建连接矩阵的信息，再调用creatMGraph（）函数，接着进入菜单，然后再选择输入一个数确定是要输出连接矩阵还是最小生成树及代价，最后选择输入确定字母y或N确定是否继续。

（2）.邻接矩阵定义模块代码

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;

}

程序解释：

用typedefstruct定义连接矩阵，通过二维数组来存储连接矩阵，并设定参数的最大值为20。

（3）.创建链接矩阵模块代码

intcreatMGraph_L（MGraph_L&G）{

charv1,v2;

inti,j,w;

cout<<"…………创建无向图（城市分布图）…………"<

（46）不包括“（）”"<

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

for（i=0;i!

=G.vexnum;++i）

{

cout<<"输入顶点（城市）"<

cin>>G.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<<"输入一条边依附的顶点（城市）和权（距离）:

（ab3）不包括“（）”"<

cin>>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邻接矩阵创建成功！

"<

returnG.vexnum;

}

程序解释：

该语句是从键盘输入顶点数和边数，输入顶点和权值，通过循环语句的调用，最后调用creatMGraph_L（）创建连接矩阵

（4）.最小生成树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]

=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]=g[k][j];

prevex[j]=k;

}

printf（"\n"）;

}

cout<<"最少生成树的代价:

";

cout<

return0;

}

程序解释：

该语句运用一系列的循环语句来实现的，利用前面的创建好的链接矩阵，通过各边权值的比较，最后调用prim（）函数，实现最小生成树的生成，同时运用sum把最小生成树各边权值相加得到最小生成树的代价。

5系统调试

1、运行程序后，初界面：

2、输入顶点和弧的个数后的界面：

.

3、输入顶点后的界面：

4、输入一条边依附的顶点和权值后的界面：

5、输入确定数字0及确定字母y后的界面：

6、输入确定数字1及确定字母n后的界面：

小结

回顾起此次课程设计，至今我仍感慨颇多，从理论到实践，在整整一周的日子里，我学到很多很多的东西，不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的内容。

培养了独立思考，深入研究，分析问题、解决问题的能力，提高综合运用本课程所学知识的能力，还对课程设计的基的设计方法、步骤、思路、有了深刻的了解与认识，并对存储结构和函数的调用，比如连接矩阵、链接表、树、图等存储结构，for引导的循环语句，特别是Prim算法理解的更深。

我本次课程设计的题目是构造可以使n个城市连接的最小生成树，开始看到题目觉得自己题目对自己比较有利，因为自己对最小生成树这节的内容比较熟悉，但是刚一开始编程觉得自己无从下手，这就看出自己的问题了，在书本上学的只是一些很肤浅的东西，在实际运用中显得很无力，但是通过自己慢慢查阅相关书籍和相关网站后，编程的进度慢慢加快了，一些相关的难点逐步得到解决，最终还是完成了此次课程设计中最主要的几个步骤。

通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才是真正的知识，才能提高自己的实际动手能力和独立思考的能力。

在设计的过程遇到了各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计，把以前所学过的知识重新温故，巩固了所学的知识。

源程序

#include

#include

usingnamespacestd;

#defineint_max10000//最大的顶点数

#defineinf9999//将无法到达的权值无限大设为9999

#definemax20

//…………………………………………邻接矩阵定义……………………

typedefstructArcCell

{

intadj;

char*info;

}ArcCell,AdjMatrix[20][20];

typedefstruct

{

charvexs[20];

AdjMatrixarcs;

intvexnum,arcnum;

}MGraph_L;

//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

intlocalvex（MGraph_LG,charv）//返回V的位置

{

inti=0;

while（G.vexs[i]!

=v）

{

++i;

}

returni;

}

intcreatMGraph_L（MGraph_L&G）//创建图用邻接矩阵表示

{

charv1,v2;

inti,j,w;

printf（"请输入顶点元素：

\n"）;

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

for（i=0;i!

=G.vexnum;++i）

{

cout<<"输入顶点"<

cin>>G.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）

{

printf（"请输入边两端顶点序号和相应的权值：

\n"）;

cin>>v1>>v2>>w;//输入一条边依附的两点及权值

i=localvex（G,v1）;//确定顶点V1和V2在图中的位置

j=localvex（G,v2）;

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

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

}

cout<<"图G邻接矩阵创建成功！

"<

returnG.vexnum;

}

voidljjzprint（MGraph_LG）

{

inti,j;

for（i=0;i!

=G.vexnum;++i）

{

for（j=0;j!

=G.vexnum;++j）

cout<

cout<

}

}

intvisited[max];//访问标记

intwe;

typedefstructarcnode//边结点

{

intadjvex;//该边指向的顶点的位置

structarcnode*nextarc;//边尾相同的下一条弧

char*info;//该边信息

}arcnode;

typedefstructvnode//邻接链表顶点头接点

{

chardata;//结点信息

arcnode*firstarc;//指向第一条依附该结点的边的指针

}vnode,adjlist;

typedefstruct//图的定义

{

adjlistvertices[max];

intvexnum,arcnum;

intkind;

}algraph;

intprim（intg[][max],intn）//最小生成树PRIM算法

{

intlowcost[max],prevex[max];//LOWCOST[]存储当前集合U分别到剩余结点的最短路径

//prevex[]存储最短路径在U中的结点

inti,j,k,min;

intsum=0;

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]

=0））

{

min=lowcost[j];

k=j;

}

printf（"（%d,%d）%d\t",prevex[k]-1,k-1,min）;

sum+=min;

lowcost[k]=0;//顶点k加入U

for（j=2;j<=n;j++）//修改由顶点k到其他顶点边的权值

if（g[k][j]

{

lowcost[j]=g[k][j];

prevex[j]=k;

}

printf（"\n"）;

}

cout<<"最少生成树的代价:

";

cout<

return0;

}

voidmain（）

{

algraphgra;

MGraph_LG;

inti,d,g[20][20];

chara='a';

d=creatMGraph_L（G）;

vnodev;

cout<

若该图为非强连通图（含有多个连通分量）时"<

<<"最小生成树不存在,则显示为非法值"<

cout<<"…………………菜单……………………"<

cout<<"0、显示该图的邻接矩阵……………………"<

cout<<"1、最小生成树PRIM算法…………………"<

ints;

chary='y';

while（y='y'）

{

cout<<"请选择菜单：

"<

cin>>s;

switch（s）

{

case0:

cout<<"邻接矩阵显示如下：

"<

ljjzprint（G）;

break;

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:

"<

prim（g,d）;

break;

}

cout<

y/n:

";

cin>>y;

if（y=='n'）

break;

}

}