贪心算法与数据结构结合2——最小生成树问题：Prim算法

我曾经听说过很多人的梦想，但由于时间的消磨。这些梦想也就慢慢消退了；我也听说过很多人侃侃而谈，最后却只是谈了谈而已。人基本都是这样的，肯定都有梦想，但就是碍于时间和精力以及周遭变化原因未能继续追寻，继续前进了。所以，如果你还想奋斗，还想追寻那种美好的憧憬。请一定要坚持下去，不要放弃！
本篇是贪心算法与数据结构结合的第二篇，本篇主要介绍最小生成树问题和以及解最小生成树问题的贪心算法——Prim算法
1、最小生成树什么是生成树
设G是n阶连通图，那么T是G的生成树当且仅当T没有回路且有n-1条边。
如果生成树增加了一条不属于树的边，那么就会构成回路
就如这个图中的左边T是一棵生成树，现在加一条边e，使其构成回路，那么这个就不是个树了。
去掉圈中的任意一条边，就得到G中的另外一棵生成树T’
也就是说生成树的算法步骤是选择边；约束条件是不形成回路；截止条件是边数达到n-1
生成树在网络中有着重要应用
下面介绍最小生成树
什么是最小生成树
给定一个无向连通带权图G=(V,E,W)，其中w(e)∈W是边e的权。
G的一棵生成树T是包含了G所有顶点的树，树中各边的权之和W(T)称为树的权，具有最小权的生成树成为G的最小生成树
我们看个例子：
我们看到啊左边的图是一个无向带权连通图，总共有10条边，E集合里面是连接这些边的两个端点的集合。右边是它的一棵最小生成树，我们可以通过计算得出，右边的这个生成树的权值之和是产生所有生成树里最小的一棵。
而对于求解最小生成树问题，我们可以用贪心法来解
这个贪心法有Prim算法和算法。
我们首先看Prim算法
2、Prim算法什么是Prim算法
输入：图G=(V,E,W),V={1,2,…,n}
输出：最小生成树T
1、初始将顶点1添加到集合S里
2、选择连接S与V-S集合最短边e={i,j}，i∈S，j∈V-S，将e加入树T，j加入S
3、继续上述过程，直到S=V为止。
下面我们来看个例子：
下面我们用Prim算法来解：
初始将顶点1添加到S集合里
此时V-S={2，3，4，5，6}，我们要再从V-S里面挑选一个点使其与顶点1构成最短边
从图中可以看到，顶点1与顶点2连接的边长度是6，顶点1与顶点3连接的边长度是1，顶点1与顶点4连接的边长度是5 。显然那个长度是1最短。
因此我们把顶点3挑进来到集合S里
现在V-S={2，4，5，6}
现在因为3加到了S集合里，那么可以在S集合找到一个点，在V-S集合中找到一个点，使其两个点的连线距离最短。
我们看到，1和2，1和4分别是6和5；然而与顶点3相连的线段中最短的是3与6的连接（1和3已经都选到S里了，就不应再考虑顶点1和顶点3连接的线段了）
那么把6加到集合S里
然后再从V-S集合里面挑，发现6和4之间的连线长度2是最短的，那么我们把4添加到集合S里。
然后就剩下{2，5}，从图中我们看到1和2，3和5长度都是6；而3和2的长度是5，那么我们把2添加到集合S里。
最后由于2和5距离最短是长度3，所以把5添加到集合S里。
当然上边两点连接的那个最小长度的边是要加到T里面作为最小权值。所以构成的最小生成树是这样的
将这些边上的权值加起来就是问题的最优解
此生成树的权值是15
那么这个Prim算法对不对呢，我们接下来用数学归纳法进行证明
数学归纳法证明Prim算法
证：对于任意k
当k=1时，存在一棵最小生成树T包含边e={1，i}，其中{i，i}是所有关联1的边中权最小的。