《数据结构与算法》课程设计成果报告-PRIM算法实现.doc

河南工程学院数据结构与算法课程设计成果报告PRIM算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目PRIM算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 题目需求分析22.2 存储结构设计32.3 算法描述32.4 程序流程图53 程序清单74 测试94.1 测试数据94.2 测试结果分析105 总结11参考文献121 课程设计目标与任务1.1 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务 设计PRIM算法的相关函数库，以便在程序设计中调用，要求：（1）对给定的网和起点，实现求解最小生成树的PRIM算法；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目需求分析1题目要求：设计PRIM算法的相关函数库，以便在程序设计中调用，要求：（1）对给定的网和起点，实现求解最小生成树的PRIM算法；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2题目分析：一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。所谓的最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并且使得权值的和最小。综合以上两个概念，我们可以得出：构造连通网的最小代价生成树，即最小生成树（Minimum Cost Spanning Tree）。找连通图的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法，这里我们介绍普里姆算法。普里姆算法也是利用贪心算法来解决最小生成树的。最小生成树MST性质：假设N=（V,E）是一个连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中uU，vV-U，则必存在一颗包含边（u,v）的最小生成树。prim算法过程为：假设N=（V,E）是连通图，TE是N上最小生成树中边的集合。算法从U=u0（u0V），TE=开始，重复执行下述操作：在所有uU，vV-U的边（u，v）E中找一条代价最小的边（u0，v0）并入集合TE，同时v0 并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，TE）为N的最小生成树。2.2 存储结构设计 以二维数组的形式来存储图，我们以下图为例： 3 4 0 1 2 2 3 6 8 5 7 9 图1-1 连通图我们用下面这个数组来储存这个图：int graphVV=0,2,0,6,0, 2,0,3,8,5, 0,3,0,0,7, 6,8,0,0,9, 0,5,7,9,0其中行的序数表示顶点的序数，单个数字表示对应定点到其他定点的权值，用0来表示定点到本身和到无法直接连通的定点的权值。 2.3 算法描述（1） 创建一个集合mstSet记录已经包含在MST中的顶点。（2） 对图中的所有顶点设置一个key值，代表代价，并初始化无穷大。第一个点设置为0，以便总是能第一个取到第一个点。int minKey(int key, bool mstSet) int min =INT_MAX,min_index;for(int v=0; vV; v+) if (mstSetv=false&keyvmin) min =keyv,min_index=v; return min_index; （3） While( mstSet没有包含所有的顶点 )：（4） 从mstSet集合中剩下的顶点中，选取一个最小key的顶点u；（5） 把u加入到mstSet；for (int i = 0; i V; i+) keyi=INT_MAX,mstSeti=false;key0=0; parent0=-1; / 第一个作为树的根 / MST 有V的顶点for (int count = 0; count V-1; count+) int u = minKey(key, mstSet); / 添加到MSTSet mstSetu = true; （6） 更新所有的和u相连的那些顶点的key值。 for (int v = 0; v V; v+) if (graphuv& mstSetv = false & graphuvkeyv) parentv = u,keyv = graphuv; 2.4 程序流程图我们以图为例，看看算法的流程： 3 4 0 1 2 2 3 6 8 5 7 9 图2-1 连通图初始的mstSet为空，keys（各个点击的代价）为0, INF, INF, INF, INF, 找到其中最小的，并加入mstSet，mstSet变为：0。 然后更新和0相邻的那些顶点的key值。相邻的顶点为1和3. 更新后为 0, 2, INF, 6, INF, 下图中灰色表示 mstSet： 0 3 1 2 4 0 1 3 2 2 3 366 6 8 5 7 0 3 1 2 4 2 图2-2 最小生成树 图2-3 最小生成树 0 3 1 2 4 2 3 2 3 2 36 8 5 7 6 8 5 7 9 图2-4 最小生成树 图2-5 最小生成树 0 1 2 3 4 2 36 5 图2-6 最小生成树 通过循环结构，来一步一步实现对mstSet的添加，和对key值的选取。3 程序清单#include #includeStdAfx.h#include #define V 5 /图中顶点个数 /在metSet 的点集合中，找出最小key的点int minKey(int key, bool mstSet) int min =INT_MAX,min_index;for(int v=0; vV; v+) if (mstSetv=false&keyvmin) min =keyv,min_index=v; return min_index; / 打印MST int printMST(int parent, int n, int graphVV) printf(路径 - 权值n); for (int i = 1; i V; i+) /输出结果 printf(%d - %d %d n, parenti, i, graphiparenti); return 0; / Prim算法 void primMST(int graphVV) int parentV; /保持MST信息 int keyV; /所有顶点的代价 bool mstSetV; /当前包含在MST中点的集合 / 初始为无穷大for (int i = 0; i V; i+) keyi=INT_MAX,mstSeti=false;key0=0; parent0=-1; / 第一个作为树的根 / MST 有V的顶点for (int count = 0; count V-1; count+) int u = minKey(key, mstSet); / 添加到MSTSet mstSetu = true; /更新和相连的顶点的代价 for (int v = 0; v V; v+) /判断顶点和权值是否符合要求 if (graphuv& mstSetv = false & graphuvkeyv) parentv = u,keyv = graphuv; / 打印生成的MST printMST(parent, V, graph); int main() /*创建以下的图 2 3 (0)-(1)-(2) | / | 6| 8/ 5 |7 | / | (3)-(4) 9 */ int graphVV = 0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0; / 输出结果 primMST(graph); return 0; 4 测试4.1 测试数据 3 4 0 1 2 2 36 8 5 7 9 图31 连通图用一个数组来表示一个联通发图int graphVV = 0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0; 通过这个数组对程序的功能进行测试。4.2 测试结果分析程序的运行结果如下：图4-1 程序结果 从结果可以看出程序实现了图的最小生成树的功能，即PRIM算法的功能。前面为最小生成树的路径选取，后面为最优路径的权值。5 总结通过本次的实践，我对数据结构又有了更深的认识。使我在数据结构的选择和应用、算法的设计与实现方面得到训练，同时培养了我做培养软件工作所需要的动手能力。与此同时，增加理解和运用数据结构与算法的水平和能力，对软件的熟悉程度，明白了，在完成一个程序问题时，需要足够的耐心和信心，面对问题要静下心来，反复的思考，不能慌张和急躁，才能顺利的解决问题。而且学会了要及时翻阅书籍材料，或者向同学和老师寻求帮助，逐步的解决问题。参考文献1.严蔚敏，吴伟民编著，数据结构（C语言版），清华大学出版社，2005 2 严蔚敏，陈文博编著，数据结构及应用算法教程，清华大学出版社，2006 3 李云清，杨庆红，揭安全编著，数据结构（C语言版），人民邮电出版社2006 4、谭浩强，张基温，唐永炎编著，C语言程序设计教程（第二版）高等教育出版社，2005 5 苏仕华等编著，数据结构课程设计，上海；机械工业出版社，2004#include #includeStdAfx.h#include #define V 5 /图中顶点个数 /在metSet 的点集合中，找出最小key的点int minKey(int key, bool mstSet) int min =INT_MAX,min_index;for(int v=0; vV; v+) if (mstSetv=false&keyvmin) min =keyv,min_index=v; return min_index; / 打印MST int printMST(int parent, int n, int graphVV) printf(路径 - 权值n); for (int i = 1; i V; i+) /输出结果 printf(%d - %d %d n, parenti, i, graphiparenti); return 0; / Prim算法 void primMST(int graphVV) int parentV; /保持MST信息 int keyV; /所有顶点的代价 bool mstSetV; /当前包含在MST中点的集合 / 初始为无穷大for (int i = 0; i V; i+) keyi=INT_MAX,mstSeti=false;key0=0; parent0=-1; / 第一个作为树的根 / MST 有V的顶点for (int count = 0; count V-1; count+) int u = minKey(key, mstSet); / 添加到MSTSet mstSetu = true; /更新和相连的顶点的代价 for (int v = 0; v V; v+) /判断顶点和权值是否符合要求 if (graphuv& mstSetv = fa