- 1、本文档共19页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
最小生成树求解-课程设计
数 据 结 构 与 算 法
课 程 设 计 报 告
PAGE
PAGE - 19 -
合肥学院
计算机科学与技术系
课程设计报告
2009~2010 学年 第 二 学期
课程 数据结构与算法课程设计名称最小生成树求解学生姓名学号0804012023专业班级08计科(2)班指导教师
2010年 6月
课程设计题目
对任意给定的网和起点,用PRIM算法的基本思想求解出所有的最小生成树。
问题分析和任务定义
本课程设计重在使用prim算法实现任意给定的网和起点的图的所有最小生成树的求解,实现本课程设计的关键即是能够掌握prim算法的思想,并能够灵活使用。
首先我们必须对prim算法有个清晰地认识,prim算法是普利姆(Prime)于1957年提出了一种构造最小生成树的算法,算法的主要思想如下:按照将顶点逐个连通的步骤,把顶点加入到已经连通的顶点集合U中,最后使得U成为最小生成树。
PRIM思路:1)初始化顶点集合U为空集。
2)任意选取一个顶点v加入U。
3)选取一条权值最小的边(u,v),其中u∈U,v∈(V-U),将该边假如到生成树,v加入到U中。
4)重复步骤3),直到所有顶点均加入到U中构成一颗最小生成树。
为了实现这一算法需要附设一个辅助数组closedge[v]用来存储从U到V-U之间具有最小代价的边。对于每个顶点 v∈(V-U),在closedge,树组中都存在一个分量closedge[v],它有两个域组成。其中一个是权值,即:
closedge[v].lowcost=MIN{cost(u,v)|u∈U},另外一个是顶点域vexs,存储依附于该边在U中的顶点。
其次,针对本课程设计的题目要求,我们需要考虑到五个问题:
如何选择、设计一个合适的算法来建立图,用以实现接下来的操作。
如何正确的在本实验中使用prim算法。
对于本课程设计中的需要,求出对于给定任意给定的网和结点,得出所有的最小生成树,关键在于需要求出所有的最小生成树,需要灵活使用prim算法实现。
对于一些细节也是需要考虑斟酌的,比如,当所输入的顶点不存在时,需要一个示语句警示,并能够重新输入。
当算法设计完成后,还需对于整个运行程序的运行界面,提示语句以及如何完美、清楚的输出各个最小生成树设计一番。
最后,在课程设计过程中,自己需要做好充足的准备工作,吃透课本中关于prim算法的解释说明,同时把握好时间,掌握整个课程设计的进度,做好整体规划,保证本次课程设计可以及时的、成功的设计出来。
数据结构的选择和概要设计
对于本次设计,在prim算法中使用的图均为无向图,对于各顶点之间的权值以及连通关系是采用邻接矩阵来实现的。同时在prim算法中采用了辅助数组closedge[v],主要用来存储到顶点的最小边权值。
建立图的数据结构类型如下:
typedef struct{
int vexs[MAX]; //顶点信息集合
int arcs[MAX][MAX]; //各边的权值
int vexnum; //顶点数
int arcnum; //边数
}MGraph; //图类型
建立辅助数组结构类型如下:
struct closed{
int adjvex; //依附于最小权值边在顶点集合U中的顶点
int lowcost; //存储最小边的权值
};
closed closedge[MAX];
整个算法概要设计主要在于图的初始化,以及如何求出所有最小生成树。下面我们可以通过相应的流程图来清楚的理解。
刚开始时初始化各顶点的顶点域、权值域赋值的算法流程:
开始
把1赋给j
判断j是否等于输入的顶点数值
j不等于I
把I的值赋给j的顶点域里;
把邻接矩阵中处于[j][I]位置的值赋给j的权值域中。
j等于I
把j+1赋给j
判断j是否小于等于图的顶点数
小于等于
大于
把0赋给顶点I的权值域
.求出最小代价的边的算法流程:
把1赋给j
把1赋给i
把邻接矩阵中处于[1][i]位置的值赋给i的权值域中;
把1赋给i的顶点域中
把i+1赋给i
判断i是否小于图的顶点数
小于
大于等于
把0赋给1的顶点域中,
把1赋给j
此时j的权值域是否小于min
j的顶点域是否等于0
j的顶点域是否等于0
把1赋给j
把100赋给min,把i的值赋给k.
把1赋给i
有一个条件不满足 都是肯定的回答
把顶点j里的权
文档评论(0)