最小生成树的普里姆算法课设

数据结构课程设计

设计说明书

最小生成树普里姆算法的实现

学生姓名 学 号 班 级 成 绩 指导教师

数学与计算机科学学院 2013年3月15日

课程设计任务书

2012—2013学年第二学期

课程设计名称： 数据结构课程设计 课程设计题目： 最小生成树普里姆算法的实现 完 成 期 限： 设计内容：

自 2013年 3 月4日至 2013年 3 月 15 日共 2 周

图论中，对于个带权的连通图，其每个生成树所有边上的权值之和可能不同，把其所有边上权值之和最小的生成树称为图的最小生成树。通讯线路铺设造价最优问题就是最小生成树的实际应用。

普里姆算法的的基本思想：从连通网N={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边(U0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网中的所有顶点都加入到生成树顶点集合U中为止。 本课程设计中主要完成以下内容： 1.任意给出一个带权值的连通网络图，能够遍历图中的所有节点。 2. 根据普里姆算法思想，编程实现此连通图的最小生成树的输出。 3.计算讨论算法的时间复杂度及空间复杂度。 基本要求如下： 1.程序设计界面友好；2.设计思想阐述清晰；3.算法流程图正确；4.软件测试方案合理、有效。 指导教师： 教研室负责人：

课程设计评阅

评语： 指导教师签名： 年 月 日

摘 要

本课题以Visual C++ 6.0作为开发环境，编程实现了连通网中的最短路径算法。该程序操作简单，界面清晰，易于掌握和理解。

关键词：普里姆算法；连通络网；Visual C++ 6.0；最短路径

目 录

1 课题描述 ........................................................................................................................................................... 1 2 算法描述 ........................................................................................................................................................... 2 2．1算法思想 ............................................................................................................................................... 2 2．2最小生成树生成过程 ........................................................................................................................... 3 2．3普里姆算法 ........................................................................................................................................... 4 2．4需要解决的问题 ................................................................................................................................... 4 2．5解决问题的方法 ................................................................................................................................... 5 3 流程图 ............................................................................................................................................................... 6 4 程序源代码 ..................................................................................................................................................... 11 5 程序测试 ......................................................................................................................................................... 15 6总结 .................................................................................................................................................................. 19 参考文献 ............................................................................................................................................................. 20

1 课题描述

在我们的平时生活中，人们都希望花最少的时间或者最少的金钱将一件事情办成，例如：一个邮递员想走最短的路把手中的物件送到收件人手中，通信公司想花费最少的金钱把通信网络覆盖在n个城市之间，这些都可归纳为求最短路径问题。

本课题利用普里姆算法来实现各城市之间铺设煤气管道连通网络中各种连接方式中的最短路径问题，从而达到一条最优线路，以使金钱或时间的花费最小，达到解决成本的目的。

开发工具：visual c++ 6.0

1

2 算法描述

本设计是基于最小生成树普里姆算法的思想上，以实现在网络中可以选择出最短线路，

从而达到省时省力的效果。

2.1算法思想

普里姆算法的基本思想：从连通网络 N = { V, E }中的某一顶点 u0 出发, 选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在 U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合 U 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。

存储方式：采用邻接矩阵作为图的存储表示

假设要在n个城市之间建立通信联络网，则联通n个城市只需要n-1条线路，然而n个城市之间最多可能设置n(n-1)/2条线路，此时，自然会考虑一个问题，如何在这些可能的线路中选择n-1条，使的在最节省经费的前提下建立起这个通信网。这就可以简化为构造联通网的最小代价生成树（简称 最小生成树）问题。

任务：根据普里姆的算法思想，输出连通网络图的最小生成树。

2

2.2最小生成树生成过程

普里姆算法最小生成树生成过程的图示如图2.1所示：

3

2.3普里姆算法

void MiniSpanTree_PRIM(Graph G,VertexType u) {

//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。 //记录从顶点集U到V-U的代价最小边的辅助数组定义： //struct {

// Vertextype adjvex; // VRType lowcost;

// }closedege[MAX_VERTEX_NUM]; k=LocateVex (G, u);

for(j=0;j

if(j!=k) closedge[j]={u, G.arcs[k][j].adj}; //{adjvex, lowcost } closedge[k].lowcost=0; /* 初始，U={u} */

for(i=1;i

closedge[k].lowcost=0; /* 第k顶点并入U集 */

for(j=0;j<=G.vexnum;++j)

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

}

}// MiniSpanTree

2.4需要解决的问题

PRIM算法中需要解决的两个问题：①在无向网中，当出现从一个顶点到其它顶点时，若其边上的权值相等，则可能从某一起点出发时会得出不同的最小生成树，但最小生成树的权必定都相等，此时我们应该怎样将所有的最小生成树求解出来；

②每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次（1≤k≤n-1）前，生成树T中已有k个顶点和k-1条边，此时T中到T外的所有边数为k(n-k)，当然它也包括两顶点间没有直接边相联，其权值被看做常量INFINIT的边在内，从如此多的边中查找最短边，其时间复杂度为O(k(n-k))，显然是很费时的，是否有一种好的方法能够降低查找最短边的时间复杂度。

4

2.5解决问题的方法

针对①中出现的问题可以通过在算法中实现，详情请看PRIM算法的基本思想； 针对②中出现的问题，通过对PRIM算法的分析，可以使查找最短边的时间复杂度降低到O(n-k)。具体方法是假定在进行第k次前已经保留着从T中到T外的每一顶点（共n-k个顶点）的各一条最短边，进行第k次时，首先从这n-k条最短边中，找出一条最最短的边，它就是从T中到T外的所有边中的最短边，假设为（i,j），此步需进行n-k次比较；然后把边（i,j）和顶点j分别并入T中的边集TE和顶点集U中，此时T外只有n-(k+1)个顶点，对于其中的每个顶点t，若（j,t）边上的权值小于已保留的从原T中到顶点t的最短边的权值，则用（j,t）修改之，使从T中到T外顶点t的最短边为（j,t），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点t的各一条最短边都保留下来了，为进行第k+1次运算做好了准备，此步需进行n-k-1次比较。所以，利用此方法求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。

5

3 流程图

1) 主函数流程图如图3 .1所示：

开始 显示菜单，进行选择 输出函数put() 退出系统 示例帮助（example()） break break 谢谢使用! 结束

图 3.1 主函数流程图

6

2) 无向图的建立及初始化流程图如图3.2所示

开始 int i=1,j=1,start,end,,weight 输入图的顶点和弧数 i<=G->vexnumN Y N j<=G->vexnumY G->arcs[i][j]=INFINITY;j++ 输入弧的两个顶点和权值 G->arcs[start][end]=weight; G->arcs[end][start]=weight; 结束 图 3. 2 无向图的建立及初始化

7

3) MiniSpanTree_PRIM函数流程图如图3.3所示

8

4) minimum函数流程图如图3.4所示

开始 int i=1,w,p; w=INFINITY i<=vnum- N Y N cl[i].lowcost!=0&&cl[i].lowcost

图 3.4 minimum函数流程图

9

5) put函数流程图如图3.5所示

开始 char j=’y’;int u; j!=’N’&&j!=’n’ Y CreateGraph(&G) j!=’N’&&j!=’n’ Y 输入开始的顶点 调用MiniSpanTree_PRIM(&G,u)函数 Y 是否从别的点开始？ Y N 构造完成，是否继续？ N 继续选择 结束

图3.5 put函数流程图

10

4 程序源代码

#include #include #include

#define INFINITY 30000 /* 定义一个权值的最大值 */ #define MAX_VERTEX_NUM 20 /* 图的最大顶点数 */ typedef struct

{int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /* 邻接矩阵 */ int vexnum,arcnum; /* 图的当前顶点和边数 */ }Graph; typedef struct

{int adjvex; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */ int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */ }ClosEdge[MAX_VERTEX_NUM]; /* 用普里姆算法求最小生成树时的辅助数组 */ void CreateGraph(Graph *G) {/* 构造邻接矩阵结构的图G */ int i,j;

int start,end,weight;

printf(\请输入图的顶点和弧数(逗号隔开):\

scanf(\输入图的顶点数和边数 */ for(i=1;i<=G->vexnum;i++) for(j=1;j<=G->vexnum;j++)

G->arcs[i][j]=INFINITY; /* 初始化邻接矩阵 */ printf(\输入顶点和其权值，格式：顶点1,顶点2,权值\\n\ for(i=1;i<=G->arcnum;i++)

{printf(\请输入第%d条弧的两个端点及权值(逗号隔开):\

scanf(\输入边的起点和终点及权值 */

G->arcs[start][end]=weight; G->arcs[end][start]=weight; } }

int minimum(ClosEdge cl,int vnum)

{/* 在辅助数组cl[vnum]中选择权值最小的顶点，并返回其位置 */

11

int i; int w,p; w=INFINITY; for(i=1;i<=vnum;i++)

if(cl[i].lowcost!=0&&cl[i].lowcost

void MiniSpanTree_PRIM(Graph *G,int u) {/* 从第u个顶点出发构造图G的最小生成树 */ ClosEdge closedge; int i,j,k,n=0,a=0;

printf(\最小代价生成树:\\n\

for(j=1;j<=G->vexnum;j++) /* 辅助数组初始化 */ if(j!=u)

{closedge[j].adjvex=u;

closedge[j].lowcost=G->arcs[u][j]; }

closedge[u].lowcost=0; /* 初始，U={u} */

for(i=1;ivexnum;i++) /* 选择其余的G->vexnum-1个顶点 */ {k=minimum(closedge,G->vexnum); /* 求出生成树的下一个顶点 */

printf(\ %d\\n\/* 输出生成树的边及其权值 */

n=n+closedge[k].lowcost;

closedge[k].lowcost=0; /* 第k顶点并入U集 */

for(j=1;j<=G->vexnum;j++) /* 新顶点并入U后，修改辅助数组*/ if(G->arcs[k][j]

closedge[j].lowcost=G->arcs[k][j]; } }

void example() {

12

}a=a+n;printf(\最小权值为:%d\\n\

/* ------------------程序解说---------------------------- */ printf(\本程序将演示构造图的最小代价生成树。\\n\

printf(\首先输入图的顶点数和弧数\\n格式：顶点数，弧数；例如:4,4\\n\ printf(\接着输入各条弧(弧尾,弧头)和弧的权值。\\n\

printf(\格式:顶点1,顶点2,权值；例如\\n1,2,1\\n1,3,2\\n2,4,3\\n3,4,4\\n\ printf(\程序将会构造该图的最小代价生成树。\\n\

printf(\并显示该最小生成树。\\n<1--2> 1\\n<1--3> 2\\n<2--4> 3\\n最小权值为:6\\n\ printf(\请继续选择:\

/* ------------------------------------------------------ */ } void put()

{Graph G; /* 采用邻接矩阵结构的图 */ char j='y'; int u;

while(j!='N'&&j!='n') {

CreateGraph(&G); /* 生成邻接矩阵结构的图 */ while(j!='N'&&j!='n') {

printf(\从哪一顶点开始:\

scanf(\ /* 输入普里姆算法中的起始顶点 */ MiniSpanTree_PRIM(&G,u); /* 普里姆算法求最小生成树 */

printf(\要继续从别的点进行构造最小代价生成树吗?(Y/N)\ fflush(stdin); /*清除缓冲区*/

scanf(\

}

printf(\最小代价生成树构造完毕，继续进行吗?(Y/N)\ fflush(stdin); /*清除缓冲区*/ scanf(\

if(j=='N'||j=='n') printf(\请继续选择:\

} }

void main() {

13

int k,i=0;

printf(\普里姆算法实现最小生成树***************\\n\

printf(\ 1.构造最小代价生成树\\n\printf(\ 2.查看帮助示例\\n\printf(\ 3.退出系统\\n\

printf(\

printf(\请选择:\

for(;k!=-1;) {

switch(scanf(\ {

case 1:put();break;

case 2:example();break;

case 3:printf(\谢谢使用!\\n\

default:printf(\输入有误!\\n请继续选择:\ }

} }

14

5 程序测试

运行以上程序，得到程序主界面，选择1，输入相关数据，得到如图5. 1所示的运行界面：

图5. 1 最小生成树运行界面

15

选择查看帮助示例得到如图5. 2所示运行界面:

图5. 2 示例帮助

运行程序，当用户选择有误，提示异常，得到如图5. 3所示运行结果:

图5. 3 错误警告

16

运行以上程序，得到程序主界面，输入相关数据，得到如图5. 4所示的运行界面

17

图5. 4 运行界面

18

6总结

本次课程设计我主要是应用了数据结构和C语言里的一些知识，综合起来完成了本次课设，虽然程序很小，但却付出了很多。

尽管在大一学C的时候也做图形界面的程序,但是经过很长时间没有去用他,发现自己已经不是很熟悉了.这次的设计我又重新学习了C环境下图形函数的使用.在用普里姆算法做最小生成树的时候在不太理解的情况下又重新仔细的按照课本上的原理最终写出了Prim算法. 所以说每次的课程设计对我们计算机专业的学生来说时必要的,让我们逐渐写大的程序积累了宝贵的经验.特别是我发现程序还是要经常写,不然突然写起代码来会有点无从下手的感觉。

本次课设的任务是完成最小生成树普里姆算法的实现，通过这次课程设计，首先让我体会到了该算法的实用性和简便性，也对该算法有了一个全新的认识和理解，让我把以前学习的知识得到巩固和进一步的认识；再次，在程序的编写过程中，也遇到了许多的问题，我们通过小组成员的讨论，问题最终得到了解决，让我意识到团队合作的重要性。

除此之外，通过这次课程设计，我发现了自己在编程方面还有很多的不足之处，加上现代社会科技发展的日新月异，计算机行业信息的更新程度之快，让我意识到我们更应该严格要求自己，时刻提醒自己提高自己的专业水平和自身的综合素质，只有这样，才不会被这个日新月异，迅速发展的社会所淘汰，才能够在未来找到自己的一块栖息地。

19

参考文献

[1] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2011 [2] 谭浩强.C语言程序设计教程（第四版)[M].清华大学出版社,2011 [3] 耿国华.数据结构c语言描述[M].西安电子科技大学出版社,2004 [4] 徐孝凯.数据结构实用教程[M].清华大学出版社,2005

20

21

本文来源：https://www.bwwdw.com/article/em16.html