数据结构课程设计
设计说明书
最小生成树普里姆算法的实现
学生姓名 学 号 班 级 成 绩 指导教师
数学与计算机科学学院 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