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

最近更新

2025年度展览公司艺术品借展代理合同 9页

2025年度小吃街店铺整体打包转让及管理协议 8页

工程项目检查总结(6篇) 19页

建筑工程专业毕业实习报告(6篇) 27页

感恩与心态的演讲稿(12篇) 21页

2025年度家庭内部房产租赁与收益分配协议 8页

2025年度家居用品区域代理合作协议 9页

2025年度室内装饰设计施工安全文明施工管理协.. 8页

2025年度实验室装修与实验室废弃物处理合同 9页

2025年度学生食堂节能减排项目合作协议 9页

2025年度学校教室地板砖施工及翻新合同 9页

2025年度婚礼小细节婚后夫妻情感培养与家庭和.. 8页

2025年度婚内夫妻借款协议附电子模板及债务风.. 10页

水利工程渣土运输合同范本3篇 50页

橡胶制品氨水配送协议3篇 51页

中空吹塑工艺介绍 34页

杭州市珠宝店租赁合同3篇 46页

2025届绵阳一诊 数学试卷 4页

中考易混词汇辨析:can could 2页

这次我没有作文初三 2页

2025年海绵项目建议书 62页

2025年(完整版)《人力资源管理》试题及答案 7页

2025年工程竣工自评报告三篇 19页

《高等教育学》考试卷参考答案 5页

深基坑工程施工安全检查验收表 4页

水土保持方案范文5篇 16页

工业工程概论复习题(必过) 14页

苹果采摘机械手设计【水果采摘机】(含CAD图纸.. 38页

旋刀式割草机的改进设计【旋刀式割草机的设计.. 19页

休克课件 94页