1 / 7
文档名称:

寻找最小生成树Prim算法.ppt

格式:ppt   大小:269KB   页数:7页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

寻找最小生成树Prim算法.ppt

上传人:weizifan339913 2019/2/27 文件大小:269 KB

下载得到文件列表

寻找最小生成树Prim算法.ppt

文档介绍

文档介绍:寻找最小生成树的Prim算法无向图的生成树:是该图的一个子图,且是包含图中所有结点的一颗树带权图中子图的权:子图所有边权之和最小生成树(MST):权最小的生成树如果不是连通图,则只有生成森林。生成森林可以通过连通部件的生成树得到Date1寻找最小生成树的Prim算法(续)Prim_MST(V,E,,r)VT:={r};dr:=0;forallvV-VTdoif((r,v)E)dv:=(r,v);elsedv:=;endforwhileVTVdo寻找一个u,使得du=min{dv:vV-VT};VT:=VT{u};forallvV-VTdodv:=min(dv,(u,v));endwhileDate2寻找最小生成树的Prim算法(续)Date3寻找最小生成树的Prim算法(续)Date4寻找最小生成树的Prim算法(续)Date5寻找最小生成树的Prim算法(续)在每次外迭代上,在进程k上计算dk,u=min{dk,v:v(V-VT)Vk}通过多对一归约将所有dk,u中的最小值du归约到进程P0进程P0通过多对一广播将u广播到所有进程每个进程看结点u是否是存储在本进程上,如果是,则将其加入VT每个进程为其上的局部结点更新d值Date6寻找最小生成树的Prim算法(续)并行执行时间为Tp=(n2/p)+(nlogp)等效率函数就是W=(p2log2p)Date7

最近更新

一年级语文上册古诗一首悯农 40页

催化裂化同轴式反应器提升管管系热补偿设计的.. 2页

供水价格反映物价波动的必要性及其计算方法 2页

低碳马氏体在自行车中轴棍生产中的应用 2页

低压电源自动投入装置要求解析(续完) 2页

煤炭租赁合同范本 6页

企业人工成本管理问题及对策研究分析 2页

游泳池安全防护承包合同标准范本教学用 6页

混凝土浇筑劳务分包合同高层建筑 6页

从流体动压润滑观点分析内燃机活塞环断面的几.. 2页

深圳公司劳动合同范本 7页

《蟋蟀的住宅》课堂演示课件 26页

海运出口货物订舱代理合同条款 6页

海上原油运输合同条款 6页

产出剖面测井异常资料的现场分析与判断 2页

五万吨年丙烯腈引进装置三废治理技术简介 2页

二氧化铅电极上氧发生反应的交流阻抗研究 2页

了解储集层基本参数是测井分析的第一步 2页

乙脑减毒活疫苗免疫机理的研究 2页

水产养殖承包合同书 6页

民政局标准合同离婚模板 6页

毕业实习聘用合同模板 6页

中小企业信用担保信息系统分析与设计 2页

中国设备管理协会在南昌召开设备改造经验交流.. 2页

森林公园娱乐项目承包经营合同 6页

中国地表水流域水环境风险分区方案研究 2页

中原经济区域内经济协调发展的对策研究 2页

两信道物联网协议分析仪的设计与实现 2页

丙溴·毒死蜱30%乳油气相色谱分析 2页

不同负载铁基载氧体的制备与性能研究 2页