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

最近更新

单片集成VF原理及其在工程中的应用 2页

单板计算机在位置自动控制系统中的应用 2页

2025年成人 cardiac 围术期综合护理策略 42页

私募基金投资合同范本 7页

私人房屋买卖合同示范文本 6页

半导体少长针消雷器在油库防雷中的应用 2页

十省市建筑财务成本研究会在无锡市召开 2页

皮肤纤维化疾病机制研究-全面剖析 32页

医疗信息系统备份容灾解决方案及其对策 2页

2025年宝宝成长免疫守护神 46页

2025年医疗过错引发的疾病探秘 66页

2025年儿科住院患者全方位护理指南 79页

2025年中枢神经系统激活剂研究进展 36页

2025年颅内动脉瘤治疗麻醉策略探究 24页

2025年腔镜下胆囊摘除手术全解析 33页

2025年胶质瘤术后康复护理指南 22页

2025年肺部积水治疗攻略 33页

2025年肺炎患者专业护理攻略 26页

2025年肝脏移植手术麻醉管理策略 54页

2025年精准治疗口服药靶向药物新进展 16页

2025年甲功检测项目与健康评估解读 10页

被沙雕网友玩坏的 “不被定义文学” 3页

2025年抗菌药物使用新规对比解析 40页

2025年感冒中医西医辨证治疗攻略 16页

潮流服饰店装饰合同模板3篇 51页

滑雪场改造包工协议3篇 58页

2025年安徽省初中学业水平考试名校联考(一)数.. 2页

初三毕业班2025届中考数学复习计划2 5页

2023-2024学年度人教版小升初小学数学考试卷 4页

篮球比赛计分表版 2页