logo资料库

最小生成树普利姆算法的实现.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.31M 资料格式：doc 举报 版权申诉
第1页 / 共25页
第2页 / 共25页
第3页 / 共25页
第4页 / 共25页
第5页 / 共25页
第6页 / 共25页
第7页 / 共25页
第8页 / 共25页
资料共25页，剩余部分请下载后查看
    1.课题的描述
    2.设计过程
    2.1 问题的分析与任务的制定
    2.2 需要解决的问题
    2.3 设计本程序的主要思想
    2.4 分模块分析
    2.5流程图
    3.程序测试与分析
    总 结
    致 谢
    参考文献
    附录
    数据结构课程设计 设计说明书 最小生成树普利姆算法的实现 学 生 姓 名 学 班 成 号 级 绩 指 导 教 师 数学与计算机科学学院 年 月 日 1
    数据结构 课程设计评阅书 题目 学生姓名 最小生成树普里姆算法的实现 学号 指导教师评语及成绩 答辩评语及成绩 教研室意见 总成绩： 指导教师签名： 年 月 日 答辩教师签名： 年 月 日 室主任签名： 年 月 日 2
    课程设计任务书 2011 —2012 学年第 二 学期 专业： 学号： 姓名： 课程设计名称： 设计题目： 数据结构课程设计 最小生成树普利姆算法的实现 完成期限：自 年 月 日至 年 月 日共 周 设计依据、要求及主要内容： 在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生 成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生 成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小 生成树问题。 普里姆算法的基本思想：从连通网络 N = { V, E }中的某一顶点 u0 出发，选择与它关 联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合 U 中。以后每一步从一个 顶点在 U 中，而另一个顶点不在 U 中的各条边中选择权值最小的边(u, v),把该边加入到生成 树的边集 TE 中，把它的顶点加入到集合 U 中。如此重复执行，直到网络中的所有顶点都加 入到生成树顶点集合 U 中为止。 假设 G=(V，E)是一个具有 n 个顶点的带权无向连通图，T(U，TE)是 G 的最小生成树， 其中 U 是 T 的顶点集，TE 是 T 的边集，则构造 G 的最小生成树 T 的步骤如下： 1）初始状态，TE 为空，U={v0}，v0∈V； 2）在所有 u∈U，v∈V-U 的边(u，v) ∈E 中找一条代价最小的边(u′，v′)并入 TE，同时将 v′ 并入 U； 重复执行步骤（2）n-1 次，直到 U=V 为止。 要求 ：(1) 任意给出一个带权值的连通网络图，能够遍历图中的所有节点。 (2) 根据普里姆的算法思想，输出针对这个连通网络图的最小生成树。 (3) 界面友好，可操作性强。 指导教师（签字）： 批准日期： 年 月 日 教研室主任（签字）： 3
    摘 要 针对现实生活中，许多地方需要考虑到如：邮递员送信，在 n 个城市之间建立通信网 络等最短路径的问题，本应用程序正是基于这一现实问题，在 vc++的平台下，采用普里姆 算法对此作出解决，本程序主要包含 2 大模块，分别为采用邻接矩阵的存储方式建立带权的 无向网络图和利用普里姆算法对所建的网络图求最小代价生成树。它的最终目的是以最经 济、最实惠、最节约的方式解决生活中的最短路径问题，以求给人们提供更节约、更便利的 生活。 关键词：最短路径；普里姆算法；最小生成树；经济节约 4
    目 录 1.课题的描述 ....................................................... 6 2.设计过程 ......................................................... 7 2.1 问题的分析与任务的制定 ..................................... 7 2.2 需要解决的问题 ............................................. 7 2.3 设计本程序的主要思想 ....................................... 7 2.4 分模块分析 ................................................. 7 2.5 流程图 .....................................................12 3.程序测试与分析 .................................................. 13 总 结 .......................................................... 17 致 谢 ........................................................... 18 参考文献 .......................................................... 19 附录 .............................................................. 20 5
    1.课题的描述 在我们的平时生活中，人们都希望花最少的时间或者最少的金钱将一件事情办成，例如： 一个邮递员想走最短的路把手中的物件送到收件人手中，通信公司想花费最少的金钱把通信 网络覆盖在 n 个城市之间，这些都可归纳为求最短路径问题。 本课题利用普里姆算法来实现譬如通信网络中各种连接方式中的最短路径问题，从而达 到一条最优线路，以使金钱或时间的花费最小，达到解决成本的目的。 开发工具：visual c++ 6.0 6
    2.设计过程 本设计是基于最小生成树普里姆算法的思想上，以实现在网络中可以选择出最短线路， 从而达到省时省力的效果。 2.1 问题的分析与任务的制定 假设要在 n 个城市之间建立通信联络网，则联通 n 个城市只需要 n-1 条线路，然而 n 个 城市之间最多可能设置 n(n-1)/2 条线路，此时，自然会考虑一个问题，如何在这些可能的 线路中选择 n-1 条，使的在最节省经费的前提下建立起这个通信网。这就可以简化为构造联 通网的最小代价生成树（简称 最小生成树）问题。 任务：根据普里姆的算法思想，输出连通网络图的最小生成树。 2.2 需要解决的问题 （1）选择哪种存储结构建立一个带权的网络图； （2）如何实现普里姆算法的功能； （3）如何输出最小生成树； 2.3 设计本程序的主要思想 普里姆算法的基本思想：假设 N = { V, {E} }是一个联通网，TE 是 N 上最小生成树 中边的集合。算法从 U={u0}（u0∈V），TE={}开始，重复执行下属操作：在所有的 u∈U，v ∈V-U 的边（u，v）∈E 中找一条代价最小的边（u0，v0）并入集合 TE，同时 v0 并入 U，知 道 U=V 为止。此时 TE 中必有 n-1 条边，则 T=（V {TE}）为 N 的最小生成树。 2.4 分模块分析 （1）预处理部分 #include #include #include #include #define MAX 20 #define MAX_NAME 3 #define INFINITY INT_MAX 7
    （2）建立无向图 功能：要寻找最小代价生成树，选择了用邻接矩阵建立的带权无向图。 实现过程：在其函数体中，首先通过键盘输入无向图中的顶点数和边数，然后通过 二重 for 循环初始化邻接矩阵，调用函数 Locate()求出每条边所对应的 两个顶点在顶点向量表中的位置后，将对应在邻接矩阵中的相应位置赋 予权值，从而在邻接矩阵中存放了相关连的顶点之间边的权值，完成无 向网的建立。 代码如下： int CreateDN(MGraph &G) { int i,j,k,w; VertexType va,vb; // 采用数组(邻接矩阵)表示法,构造无向图 G。 printf("\t\t 请输入无向图的顶点数和边数: "); scanf("%d%d",&G.vexnum,&G.arcnum); if(G.vexnum<=1) { } printf("\t\t 最小生成树不存在!"); return 0; printf("\t\t 请依次输入%d 个顶点:",G.vexnum); for(i=0;i
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料