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

最近更新

基于FPGA的多通道高速数据采集系统设计共3 4页

培训课程研发心得体会(2) 5页

国有企业领导干部管理体制的改革完善研究十 5页

国有企业投融资风险管理问题与应对策略 4页

国有企业人力资源管理常见问题及优化策略 4页

国内轴承行业发展现状研究 4页

员工评估模板格式 4页

员工激励机制论文范文参考(老师推荐6) 4页

各种申请报告范文 4页

厨房家电项目企业经营战略方案(参考范文) 3页

单片机最小系统设计与制作报告毕业设计 4页

单位制度集锦选集【职工管理】 4页

华为公司的人力资源管理流程 4页

医院人力资源管理存在的问题及对策 3页

初级经济师工商管理考点企业组织结构形式与选.. 5页

创业过程中如何有效管理人力资源 5页

军事理论课论文参考题目 4页

公司项目管理中存在的问题及改进措施(精选5) 10页

公司安全、环保绩效考核管理制度范文 3页

公司HRM解决方案框架 4页

《实验研究法》 29页

体育田径专业毕业论文开题报告 4页

低碳经济背景下的企业可持续发展研究 4页

传统人事管理与现代人力资源开发与管理的联系.. 4页

会计学本科毕业论文开题报告通用7 4页

优秀自行车运动员不同训练手段后血乳酸的评定.. 6页

企业绩效考核的含义与作用版 7页

企业经营建议与思考 6页

企业管理创新论文摘要(15) 4页

芳纶纤维复合材料界面增强的两级实现机制研究.. 2页