关于什么是Prim（普里姆算法）?
在实际生活中，我们常常碰到类似这种一类问题:如果要在n个城市之间建立通信联络网，
则连通n个城市仅仅须要n-1条线路。这时。我们须要考虑这样一个问题。怎样在最节省经费前提
下建立这个通信网.换句话说，我们须要在这n个城市中找出一个包括全部城市的连通子图，使得
其全部边的经费之和最小. 这个问题能够转换为一个图论的问题:图中的每一个节点看成是一个城市，
节点之间的无向边表示修建该路的经费。即每条边都有其对应的权值，而我们的目标是挑选n-1条
边使全部节点保持连通。而且要使得经费之和最小.
这里存在一个显而易见的事实是: 最优解中必定不存在循环(可通过反证法证明). 因此。最后找
出的包括全部城市的连通子图必定没有环路。这样的连通且没有环路的连通图就简称为树。而在一个
连通图中删除全部的环路而形成的树叫做该图的生成树.对于城市建立通信连通网。须要找出的树由
于具有最小的经费之和。因此又被称为最小生成树(Minimum Cost Spanning Tree)，简称MST.
基本思路？
因为生成树必须包括原图里面的全部节点。关键的问题就在于边的选择，怎么才干找出n-1条边，
使得全部节点连通。而且权重最小呢？ 这里。我们先来看看MST有什么特点设有上图所看到的的最小生
成树T,假设删除边(u,v)∈T,则T将被分解成两个子树:T1和T2,因此。T1和T2各自是其所包括节点的最
小生成树。此处可用反证法证明:如果T1(也可如果为T2)不是其所包括节点的最小生成树。那么，势必
还存在的生成树T'，那么，T'+w(u,v)+T2 故结论成立. 这就是最小生成树的最优子结构性质。在细想一下，MST也包括了重叠子问题的性质，那么似乎我们 能够用动态规划来解决.但假设用动态规划来解决MST，其时间复杂度是指数级别的。显然不是太可取， 我们须要找寻更好的方法.既然MST满足最优子结构性质，那么它是否满足贪婪选择属性呢？ 为了更好地理解最小生成树请看例如以下的样例： 增加一个地区有9个城镇，镇长要求你把这九个城镇联通起来，可是要求消耗最少，就是走的路最少。 如图： 代表九个城镇。而且相邻城镇之间的道路消耗已经标了出来，要求联通全部消耗最好。 那么能够得到例如以下几种情况： 1. 总消耗：=11 + 26 + 20 + 22 + 18 + 21 + 24 + 19 = 161 2、 总消耗:=8+12+10+11+17+19+16+7= 100 3、 总消耗：=8+12 + 10+11 +16 +19 + 16 +7 = 99 综上三图可知最后一个以微小的差距赢了第二个。 这样的就叫做最小生成树。 对于Prim的算法： 设图G=(V,E),U是顶点集V的一个非空子集。假设(u,v)是一条具有最小权值的边。当中u∈U,v∈V-U, 则必存在一棵包括边(u,v)的最小生成树. 上述的性质能够通过反证法证明。假设(u,v)不包括在G的最小生成树T中。那么，T的路径中必定存 在一条连通U和V-U的边，假设将这条边以(u,v)来替换，我们将获得一个权重更低的生成树，这与T 是最小生成树矛盾.既然MST满足贪婪选择属性。那么。求解最小生成树的问题就简化了非常多。 总结一下，详细的步骤大概例如以下： 构建一棵空的最小生成树T，并将全部节点赋值为无穷大. 构建一棵空的最小生成树T。并将全部节点赋值为无穷大.任选一个节点放入T。另外一个节点集合为V-T.对V-T中节点的赋值进行更新(因为此时新增加一个节点，这些距离可能发生变化)从V-T中选择赋值最小的节点，增加T中假设V-T非空，继续步骤3～5，否则算法终结 这就是最小生成树和Prim算法的解说。 好文阅读
发表评论