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年智能社区上海商品房预售合同标准文本 8页

2025年度鱼病防治技术服务与鱼产品销售合同 9页

短期质押贷款合同实施细则 6页

2025年度高端汽车抵押消费借款协议 7页

2025年度高端培训学校课程研发权转让协议 9页

2025年度高端叉车租赁安全协议责任书(电商仓.. 9页

2025年重症监护室感染防控技能提升培训 39页

2025年度高空作业吊车租赁及安全保障协议 9页

2025年度高科技企业高管职务聘任合同 7页

2025年度高科技企业劳务雇佣合同书优质版 8页

2025年度高校毕业生就业市场推广与就业服务协.. 8页

2025年心得体会社会实践200字 22页

2025年心得体会军训的日记 7页

2025年度高新技术企业员工劳动合同简易版 8页

2025年度高新技术产业资质借用合作框架协议 8页

2025年度高新技术产业人力资源事务代理全面合.. 8页

三维打印材料-全面剖析 29页

2025年德国简单留学申请书 7页

2025年度餐饮企业服务人才招聘与培训合同 9页

目标考核责任合同书 7页

2025年度食品包装材料外协加工质量保证协议 9页

2025年药物代谢动力学研究与临床应用解析 44页

2025年度集体合同履行争议解决合同 7页

2025年腹部DWI成像技术临床应用探究 10页

上颌窦骨折的影像学诊断方法研究-全面剖析 23页

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

服装设计合作协议书 5页

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

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

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