计算机毕业论文|计算机论文|计算机毕业设计|计算机网络论文  
设为首页 加入收藏 联系站长
论文无忧网|专业的计算机论文、计算机毕业论文服务网站
计算机毕业设计 计算机毕业论文 计算机论文 管理系统 工资 在线选课 图书
当前位置:计算机毕业论文网 >> JSP论文设计 >> 浏览文章
语言动态编程实现最小生成树

【说明】本站所列作品的内容只是论文的部分介绍,如果想了解此作品的详细资料,请联系在线客服。
全套设计作品包括系统+源程序+论文+开题报告+使用手册,可以直接作为毕业设计/论文使用.
本站作品全部经过技术员测试,完整无错,大家可以放心参考使用。包调试,包指导,售后全部免费,直到您通过答辩为止。
现成作品的购买流程请参照:购买现成作品流程 网站介绍 常见问题解答

1. 普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法的比较
(1)普里姆(Prim)算法:
算法特点:该算法的特点是当前形成的集合T始终是一棵树。将T中U和TE分别看作红点和红边集,V-U看作蓝点集。算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。MST性质保证了此边是安全的。T从任意的根r开始,并逐渐生长直至U=V,即T包含了 C中所有的顶点为止。MST性质确保此时的T是G的一棵MST。因为每次添加的边是使树中的权尽可能小,因此这是一种"贪心"的策略。
算法分析:该算法的时间复杂度为 O(n )。与图中边数无关,该算法适合于稠密图
(2)克鲁斯卡尔(Kruskal)算法:
算法特点:该算法的特点是:当前形成的集合T除最后的结果外,始终是一个森林。
算法分析:该算法的时间复杂度为O(elge)。Kruskal算法的时间主要取决于边数。它较适合于稀疏图。
普里姆(Prim)算法比克鲁斯卡尔(Kruskal)算法更容易实现,而且普里姆(Prim)算法适合于稠密图,所以选择普里姆(Prim)算法构造最小生成树

 


第三章 程序设计思想


3-1 用Prim算法构造最小生成树


3-1-1 算法思想
   T=(U,TE)是存放MST的集合。①T的初值是({r},¢) 即最小生成树初始时只有一个红点r,没有红边。②T经过n-1次如下步骤操作,最后得到一棵含n个顶点,n-1条边的最小生成树⒈选择紫边集中一条轻边并扩充进T⒉将轻边连接的蓝点改红点⒊将轻边改红边⒋修改紫边集
3-1-2 较小紫边集的构造  
若当前形成的T中有k个顶点,|U|=k,|V-u|=n-k,故可能的紫边数目是k(n-k)。从如此大的紫边集中选择轻边是低效的。因此,必须构造较小的紫边集。 对于每个蓝点v ∈V-U,从v到各红点的紫边中,只有最短的那一条才有可能是轻边。因此,只须保留所有n-k个蓝点所关联的最短紫边作为轻边的候选集即可。
3-1-3 候选紫边集合的修改 
当把轻边(u,v)扩充到T时,因为v由蓝变红,故对每个剩余的蓝点j,边(v,j)就由非紫边变为紫边,这条新紫边的长度可能小于蓝点j原来所关联的最短紫边的长度。因此,用长度更小的新紫边取代那些原有的最短紫边。
用java语言动态实现此过程:
步骤:1、首先在文本框内输入城市的个数,即顶点数
2、根据输入的顶点个数点击鼠标分别显示出①②③④⑤……
3、在文本框内分别输入两个城市的名字以及权值,与此同时,在图中自动画出两点之间的连线,并在线的中央显示其权值。
4、根据求最小生成树(最短路径)的方法,用不同的颜色动态演示出它的生成过程。
5、发布到网页上。
Prim算法构造最小生成树的执行过程如下:

上一篇: 防火墙规则分析、翻译的算法研究
下一篇: 选择排序全动态图形演示程序的设计与实现
在线客服  
点击这里给我发消息 点击这里给我发消息
点击这里给我发消息 点击这里给我发消息
QQ:528311109 QQ:528311109
  服务邮箱:Service@paper51.com
热门浏览
论文降价了,2010年毕业的同学你
计算机毕业论文无忧网-公告
计算机毕业论文-论文无忧网至同学
5年信誉服务保证-计算机毕业论文
购买现成作品流程
计算机毕业论文答辩过程中需要注
付款方式
网站介绍
计算机毕业论文答辩前的准备
常见问题
最近更新  
论文降价了,2010年毕业的同学你
计算机毕业论文无忧网-公告
计算机毕业论文-论文无忧网至同学
5年信誉服务保证-计算机毕业论文
购买现成作品流程
计算机毕业论文答辩过程中需要注
付款方式
网站介绍
计算机毕业论文答辩前的准备
常见问题
设为首页 | 加入收藏 | 关于本站 | 联系站长 | 友情链接 | 版权申明 | 在线留言 | 网站地图
Copyright 2006-2008 Powered by Paper51.com,论文无忧网 All Rights Reserved.
声明:《论文无忧网》,根据《信息网络传播权保护条例》,如果我们网站上的的作品侵犯了您的权利,请及时通知我们,我们会及时删除。
《论文无忧网》为您提供优秀的计算机毕业设计|计算机毕业论文|计算机论文|毕业论文等资料,仅供学习参考使用。