首页 > 代码库 > 最小生成树之Prim算法的实现
最小生成树之Prim算法的实现
Prim算法的思想是,首先从任意一个节点出发,逐渐生成,直至该树覆盖了所有的V中的节点。
如下图:
图中的黑色的边即是最小生成树中的边。
实现Prim算法的关键便是,如何选择一条 “权值较小并且对于已有生成树中的点集合S来说是安全的边”,此处的安全指的是:
加入该边e之后,S仍然是一个树。
于是:对于图 G = (V, E) Prim的执行步骤大致为:
1 从任意节点r开始,因此将原来的顶点集合分为两部分: S = {r}, T = V-{s},
2 计算T中的节点到S中的节点的距离,即对于T中的节点v而言, d(v) = min{(u,v), u 属于S };
3 选出所有的(2)中的计算的最短的权,加入到S中,并且更新S与T中的点的集合。
4 重复2,3步,直至所有的节点都在S中,T为空。
执行完毕。
上述的步骤可由下面的简单的图解来解释:
?
因此最终的结果是17.
上述最重要的便是记录不在S中的节点到S中的最短的距离。这显然可以使用优先队列(堆)来实现,但是在选中该点之后,需要更新它的邻居节点的距离信息,即会减小
队列中的key值,这是优先队列没有实现的,于是我自行实现了一个最小堆,并且实现了Prim算法,代码如下:
<script src="https://code.csdn.net/snippets/436821.js" type="text/javascript"></script>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。