数据结构(C言语版本)课程设计报告_最小生成树的应用
22页1、武 夷 学 院 课程设计报告课程名称:数据结构C言语版本设计题目:最小生成树的应用学生班级:10计科1班学生姓名:指导教师:完成日期:2012-01-05 课程设计工程研究报告目录一、问题描述及根本要求1 -二、 实现本程序需要解决的问题如下1 -三、 测试数据2 -四、 算法思想3 -五、 模块划分4 -六、 算法设计与分析7 -七、 源程序11 -八、 测试数据14 -九、 课程设计工程进度表及任务分配表及任务分配表15 -十、 设计心得16 -十一 参考文献17 -一、为题描述及根本要求在n个城市间建立通信网络,需架设n-1条线路。求解如何以最低经济代价建设此通信网,这是一个最小生成树问题。要求:1利用普利姆算法求网的最小生成树;2输出生成树中各边及权值。 二、实现本程序需要解决的问题如下(1)、如何选择存储结构去建立一个带权网络。(2)、如何在所选存储结构下输出这个带权网络。(3)、如何实现prim算法的功能。(4)、如何从每个顶点开始找到所有的最小生成树的顶点。(5)、如何输出最小生成树的边及其权值。此问题的关键在于如何实现prim算法,实现的过程中如何得到构成最小生成树的所
2、有顶点,此外输出也是一个关键问题所在,在此过程中经过了屡次调试。首先我们对问题进行大致的概要分析:这个问题主要牵涉到通过prim的根本算法思想实现程序所要求的功能,该算法的主要思想是:假设N=V,E是连通网,TE是N上最小生成树中边的集合。算法从U=u0( u0V),TE=开始,重复执行下述操作:在所有uU,vV-U的边u,vE中找一条代价最小的边u0,v0并入集合TE,同时v0并入U,直至U=V为止。此时TE中必有n-1条边,那么T=V,E为N的最小生成树。问题的输入数据的格式为:首先提示输入带权网络的顶点边数,我定义的为整形数据型,然后输入每一条边的信息,即边的两个顶点以及权值,是十进制整数类型,这样我们就建立一个带权网络,并用邻接矩阵来存储,生成一个方阵显示出来。问题的输出数据格式为:输出是以邻接矩阵形式输出,以及从不同顶点开始生成的最小生成树。题目要求以及到达目标:题目要求用prim算法实现给定无向网中边e和顶点n实现生成的最小生成树,输出生成树中的各边及权值。三、测试数据第一组顶点数vertices、边数edge:4、5起始节点starting、下个节点terminal、权值
3、weights:1,2,11,3,22,4,53,4,41,4,6预测结果1、2、4第二组顶点数vertices、边数edge:6,10,起始节点starting、下个节点terminal、权值weights:1,2,61,3,11,4,52,3,52,5,33,5,63,4,53,6,44,6,25,6,6预测结果1、4、2、5、3 四、算法思想普里姆算法的根本思想:普里姆算法是另一种构造最小生成树的算法,它是按逐个将顶点连通的方式来构造最小生成树的。从连通网络 N = V, E 中的某一顶点 u0 出发,选择与它关联的具有最小权值的边(u0, v),将其顶点参加到生成树的顶点集合U中。以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边参加到生成树的边集TE中,把它的顶点参加到集合U中。如此重复执行,直到网络中的所有顶点都参加到生成树顶点集合U中为止。假设N=(V,E)是一个连通网,TE是N上最小生成树中边的集合。那么构造N的最小生成树的步骤如下: 1初始状态,TE为,U=u0,u0V; 2在所有uU,vV-U的边(u,v) E中找一条代价
《数据结构(C言语版本)课程设计报告_最小生成树的应用》由会员桔****分享,可在线阅读,更多相关《数据结构(C言语版本)课程设计报告_最小生成树的应用》请在金锄头文库上搜索。
2022年体育教师实习心得体会
2023年大学生实习报告范文汇总七篇
关于某工程赶工措施费的计算
服装厂管理流程
食品营养学课程论文(营养养生)
2015年河南省高一数学竞赛试题
关于风险限额管理(DOC)
2023年青海省海东市互助县加定镇社区工作人员考试模拟题及答案
2023年采购部经理的个人工作计划标准范本(3篇).doc
复习:平面直角坐标系---巩固提高
关于经营权转让合同范文十篇.doc
沪科版初中物理知识点总结归纳
北京福建企业总商会会员单位
假发项目企业运营管理模式分析
文登某医院“服务明星”评选方案
中级经济师《公路运输》考试(全考点覆盖)名师点睛卷含答案87
6.2.1分析与设计
肾功能不全怎样选择抗菌药物
监理专题安全例会纪要
简单的采购部门个人工作计划样本(五篇).doc
2023-01-08 20页
2023-01-27 71页
2023-02-24 15页
2023-07-02 43页
2023-05-02 123页
2023-11-16 5页
2023-03-28 7页
2023-07-09 41页
2023-10-14 6页
2023-12-23 123页