`
lovnet
  • 浏览: 6671442 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

prim算法实现

 
阅读更多

普里姆(Prim)算法

  1.基本思想:设G=(V, E)是具有n个顶点的连通网,T=(U, TE)是G的最小生成树, T的初始状态为U={u0}(u0∈V),TE={},重复执行下述操作:在所有u∈U,v∈V-U的边中找一条代价最小的边(u, v)并入集合TE,同时v并入U,直至U=V。即:

(1)从连通网络 G = { V, E }中的某一顶点 u0 出发,选择与它关联的具有最小权值的边(u0, v),将其顶点加入到生成树的顶点集合U中。

  (2)以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合U中为止。

示例:

昨晚上学长讲了最小生成树中的普利姆算法,不过没有将代码实现,今天纠结了一天,嘿嘿,终于搞明白了一点,这个题是一个赤裸裸的最小生成树问题,也许会有很多错误,希望有人能帮我找出.

题目:布线问题

原题地址:请猛击

AC代码:

感到不错,就从回收站里找回来了,嘿嘿……

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics