数据结构课程设计最小生成树的普里姆算法课设

1、数据结构课程设计设计说明书最小生成树普里姆算法的实现学生姓名 学 号 班 级 成 绩 指导教师 数学与计算机科学学院2013年3月15日 课程设计任务书20122013学年第二学期课程设计名称： 数据结构课程设计 课程设计题目： 最小生成树普里姆算法的实现 完 成 期 限：自 2013年 3 月4日至 2013年 3 月 15 日共 2 周设计内容：图论中，对于个带权的连通图，其每个生成树所有边上的权值之和可能不同，把其所有边上权值之和最小的生成树称为图的最小生成树。通讯线路铺设造价最优问题就是最小生成树的实际应用。 普里姆算法的的基本思想：从连通网n=v,e中的某一顶点u0出发，选择与它关联

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

3、语： 指导教师签名： 年 月 日摘 要本课题以visual c+ 6.0作为开发环境，编程实现了连通网中的最短路径算法。该程序操作简单，界面清晰，易于掌握和理解。关键词：普里姆算法；连通络网；visual c+ 6.0；最短路径目 录1 课题描述12 算法描述221算法思想222最小生成树生成过程323普里姆算法424需要解决的问题425解决问题的方法53 流程图64 程序源代码115 程序测试156总结19参考文献201 课题描述在我们的平时生活中，人们都希望花最少的时间或者最少的金钱将一件事情办成，例如：一个邮递员想走最短的路把手中的物件送到收件人手中，通信公司想花费最少的金钱把通信网络覆

4、盖在n个城市之间，这些都可归纳为求最短路径问题。 本课题利用普里姆算法来实现各城市之间铺设煤气管道连通网络中各种连接方式中的最短路径问题，从而达到一条最优线路，以使金钱或时间的花费最小，达到解决成本的目的。 开发工具：visual c+ 6.0212 算法描述 本设计是基于最小生成树普里姆算法的思想上，以实现在网络中可以选择出最短线路，从而达到省时省力的效果。2.1算法思想普里姆算法的基本思想：从连通网络 n = v, e 中的某一顶点 u0 出发, 选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点加入到生成树顶点集合u中。以后每一步从一个顶点在 u 中,而另一个顶点不在 u 中

5、的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合 u 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 u 中为止。存储方式：采用邻接矩阵作为图的存储表示假设要在n个城市之间建立通信联络网，则联通n个城市只需要n-1条线路，然而n个城市之间最多可能设置n(n-1)/2条线路，此时，自然会考虑一个问题，如何在这些可能的线路中选择n-1条，使的在最节省经费的前提下建立起这个通信网。这就可以简化为构造联通网的最小代价生成树（简称 最小生成树）问题。任务：根据普里姆的算法思想，输出连通网络图的最小生成树。2.2最小生成树生成过程 普里姆算法最小生成树生成过程的图示如图2.1

6、所示： 2.3普里姆算法void minispantree_prim(graph g,vertextype u) /用普里姆算法从第u个顶点出发构造网g的最小生成树t，输出t的各条边。/记录从顶点集u到v-u的代价最小边的辅助数组定义：/struct / vertextype adjvex;/ vrtype lowcost;/ closedegemax_vertex_num; k=locatevex (g, u); for(j=0;jg.vexnum;+j) /* 辅助数组初始化 */ if(j!=k) closedgej=u, g.arcskj.adj; /adjvex, lowcost c

7、losedgek.lowcost=0; /* 初始，u=u */ for(i=1;ig.vexnum;+i) /* 选择其余的g.vexnum-1个顶点 */ k=minimum(closedge); /* 求出生成树t的下一个顶点 */ printf(closedgek.adjvex,g.vexsk); /* 输出生成树的边 */ closedgek.lowcost=0; /* 第k顶点并入u集 */ for(j=0;j=g.vexnum;+j) if(g.arcskj.adjclosedgej.lowcost) / 新顶点并入u后重新选择最小边 closedgej = g.vexsk,g.

8、arcskj.adj ;/ minispantree2.4需要解决的问题prim算法中需要解决的两个问题：在无向网中，当出现从一个顶点到其它顶点时，若其边上的权值相等，则可能从某一起点出发时会得出不同的最小生成树，但最小生成树的权必定都相等，此时我们应该怎样将所有的最小生成树求解出来；每次如何从生成树t中到t外的所有边中，找出一条最短边。例如，在第k次（1kn-1）前，生成树t中已有k个顶点和k-1条边，此时t中到t外的所有边数为k(n-k)，当然它也包括两顶点间没有直接边相联，其权值被看做常量infinit的边在内，从如此多的边中查找最短边，其时间复杂度为o(k(n-k)，显然是很费时的，是

9、否有一种好的方法能够降低查找最短边的时间复杂度。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）边上的

10、权值小于已保留的从原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)。3 流程图1) 主函数流程图如图3 .1所示：开始显示菜单，进行选择示例帮助（example()）输出函数put()退出系统结束breakbreak谢谢使用! 图 3.1 主函数流程图2) 无向图的建立及初始化流程图如图3.2所示开始int i=1

11、,j=1,start,end,weightjvexnum-ivexnum-g-arcsij=infinity;j+nyyng-arcsstartend=weight;g-arcsendstart=weight;结束输入弧的两个顶点和权值输入图的顶点和弧数图 3. 2 无向图的建立及初始化3) minispantree_prim函数流程图如图3.3所示4) minimum函数流程图如图3.4所示开始int i=1,w,p;w=infinityi=vnum-ycli.lowcost!=0&cli.lowcostwyw=cli.lowcost;p=i;return pi+nn结束 图 3.4 min

12、imum函数流程图5) put函数流程图如图3.5所示开始char j=y;int u;j!=n&j!=ncreategraph(&g)yj!=n&j!=ny输入开始的顶点调用minispantree_prim(&g,u)函数是否从别的点开始？n构造完成，是否继续？n结束yy继续选择 图3.5 put函数流程图 4 程序源代码#include #include #include #define infinity 30000 /* 定义一个权值的最大值 */#define max_vertex_num 20 /* 图的最大顶点数 */typedef structint arcsmax_verte

13、x_nummax_vertex_num; /* 邻接矩阵 */ int vexnum,arcnum; /* 图的当前顶点和边数 */graph;typedef structint adjvex; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */ int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */closedgemax_vertex_num; /* 用普里姆算法求最小生成树时的辅助数组 */void creategraph(graph *g)/* 构造邻接矩阵结构的图g */ int i,j; int start,end,weight; pri

14、ntf(请输入图的顶点和弧数(逗号隔开):); scanf(%d,%d,&g-vexnum,&g-arcnum); /* 输入图的顶点数和边数 */ for(i=1;ivexnum;i+) for(j=1;jvexnum;j+) g-arcsij=infinity; /* 初始化邻接矩阵 */ printf(输入顶点和其权值，格式：顶点1,顶点2,权值n); for(i=1;iarcnum;i+) printf(请输入第%d条弧的两个端点及权值(逗号隔开):,i); scanf(%d,%d,%d,&start,&end,&weight); /* 输入边的起点和终点及权值 */ g-arcsst

15、artend=weight; g-arcsendstart=weight; int minimum(closedge cl,int vnum)/* 在辅助数组clvnum中选择权值最小的顶点，并返回其位置 */ int i; int w,p; w=infinity; for(i=1;i=vnum;i+) if(cli.lowcost!=0&cli.lowcostw) w=cli.lowcost;p=i; return p;void minispantree_prim(graph *g,int u)/* 从第u个顶点出发构造图g的最小生成树 */ closedge closedge; int i

16、,j,k,n=0,a=0; printf(最小代价生成树:n); for(j=1;jvexnum;j+) /* 辅助数组初始化 */ if(j!=u) closedgej.adjvex=u; closedgej.lowcost=g-arcsuj; closedgeu.lowcost=0; /* 初始，u=u */ for(i=1;ivexnum;i+) /* 选择其余的g-vexnum-1个顶点 */ k=minimum(closedge,g-vexnum); /* 求出生成树的下一个顶点 */ printf( %dn,closedgek.adjvex,k,closedgek.lowcost)

17、; /* 输出生成树的边及其权值 */n=n+closedgek.lowcost; closedgek.lowcost=0; /* 第k顶点并入u集 */ for(j=1;jvexnum;j+) /* 新顶点并入u后，修改辅助数组*/ if(g-arcskjarcskj; a=a+n;printf(最小权值为:%dn,a);void example()/* -程序解说- */ printf(本程序将演示构造图的最小代价生成树。n); printf(首先输入图的顶点数和弧数n格式：顶点数，弧数；例如:4,4n); printf(接着输入各条弧(弧尾,弧头)和弧的权值。n); printf(格式:

18、顶点1,顶点2,权值；例如n1,2,1n1,3,2n2,4,3n3,4,4n); printf(程序将会构造该图的最小代价生成树。n); printf(并显示该最小生成树。n 1n 2n 3n最小权值为:6n); printf(请继续选择:); /* - */void put()graph g; /* 采用邻接矩阵结构的图 */ char j=y; int u; while(j!=n&j!=n) creategraph(&g); /* 生成邻接矩阵结构的图 */ while(j!=n&j!=n) printf(从哪一顶点开始:); scanf(%d,&u); /* 输入普里姆算法中的起始顶点

19、*/ minispantree_prim(&g,u); /* 普里姆算法求最小生成树 */ printf(要继续从别的点进行构造最小代价生成树吗?(y/n); fflush(stdin); /*清除缓冲区*/ scanf(%c,&j); printf(最小代价生成树构造完毕，继续进行吗?(y/n); fflush(stdin); /*清除缓冲区*/ scanf(%c,&j); if(j=n|j=n) printf(请继续选择:); void main() int k,i=0; printf(*普里姆算法实现最小生成树*n);printf( 1.构造最小代价生成树n);printf( 2.查看帮

20、助示例n);printf( 3.退出系统n);printf(*n); printf(请选择:);for(;k!=-1;) switch(scanf(%d,&k),k) case 1:put();break; case 2:example();break; case 3:printf(谢谢使用!n);exit(0); default:printf(输入有误!n请继续选择:); 5 程序测试运行以上程序，得到程序主界面，选择1，输入相关数据，得到如图5. 1所示的运行界面：图5. 1 最小生成树运行界面选择查看帮助示例得到如图5. 2所示运行界面: 图5. 2 示例帮助运行程序，当用户选择有误，提示异常，得到如图5. 3所示运行结果:图5. 3 错误警告运行以上程序，得到程序主界面，输入相关数据，得到如图5. 4所示的运行界面图5. 4 运行界面6总结本次课程设计我主要是应用了数据结构和c语言里