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

最近更新

关于混流涡轮在增压器上的应用 2页

关于汞法食盐电解转换问题的探讨 2页

人教版英语高二下Unit11教学设计 30页

关于建立测量形状误差数学模型的研究 2页

2025年电工材料:电气项目合作计划书 64页

《营养配餐与食谱编制》-文件 75页

2025年癌症疼痛康复攻略 30页

关于京沪线修建高速铁路问题的探讨 2页

关于三效蒸发装置的工艺设计总结 2页

2025年护理职业行为准则详解 35页

2025年急性阑尾炎患者护理指南 54页

全钢载重子午胎成型卸胎装置设计与应用 2页

2025年宫外孕护理要点与查房教学攻略 23页

2025年多肽抗原合成与抗体研发实战解析 87页

免疫酶法检测人外周血T淋巴细胞亚群的初步探讨.. 2页

2025年全肺叶切除术后康复指南与护理要点 30页

传承家风家训弘扬传统美德演讲稿(5篇) 25页

2025年青少年心理健康评估指南 12页

关于母亲追悼词范文(11篇) 30页

冬奥带动全民上冰雪心得感悟作文(3篇) 6页

初二地理教学工作总结(33篇) 90页

大学借读申请书范文(7篇) 8页

2025年七月生产小讲颈椎病预防与治疗攻略 19页

2025年新生儿缺氧抢救攻略 51页

2025年大学中国新能源电动汽车消费者调研报告.. 24页

艺术舞蹈老师简历模板 1页

煤炭资源地质勘查设计编写提纲 14页

硫酸铵生产硫酸钾的可行性方案 31页

2022年首都经济贸易大学工商管理专业《管理学.. 22页

学生5mm坐标纸(虚线 word版)直接打印 2页