首页 > 其他 > 详细

图的最小生成树

时间:2018-02-03 19:41:43      阅读:193      评论:0      收藏:0      [点我收藏+]

Prim:适合边稠密的图

技术分享图片

设置2个数据结构:MST lowcost

我们假设V1是起始点,进行初始化(lowcost[]==-1 代表 无通路 lowcost[i]==0代表 顶点 i 加入到MST 中):

V1 加入MST  比较 其余定点到 MST 内所有顶点的权值(即:其余顶点到V1)

 lowcost[2]=6,lowcost[3]=1,lowcost[4]=5,lowcost[5]=-1,lowcost[6]=-1,明显看出,以V3为终点的边的权值最小=1,

V3 加入MST 比较 其余定点到 MST 内所有顶点的权值(即:其余顶点到V1,V3)

需要更新lowcost数组: 

lowcost[2]=5,lowcost[4]=5,lowcost[5]=6,lowcost[6]=4

V6 加入MST 比较 其余定点到 MST 内所有顶点的权值(即:其余顶点到V1,V3)

.。。。。。。。

直到所有点在MST内

dijkstra算法:

待续。。。。。。。。。

图的最小生成树

原文:https://www.cnblogs.com/Sky-Aces/p/8410414.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!