最小生成树
题图来源：http://www.nipic.com/show/3/77/30ba1a57bcec814c.html,侵删
最小生成树
在说最小生成树之前我们必须明确的几点：
- 在之前的无向图基础上给每一条边加上权值（weight）后，这个图就是加权图，每一边的权值是可以相加和可以比较大小的（权值一般是数字）
- 对于任意一棵树，欧拉给出了下面的等量关系$V = E + 1$
我还真不知道咋形容生成树是啥。这么说吧，我们把一张图看成一个交通网，顶点就是地点，边就是路，边的权值就是路的长度。现在有拆迁办来了，他们要在满足任意两地之间可以来往的基本前提（两地之间的路可以有其他的点）下只保留尽可能少数量的路。剩下的路和地点构成的图是原来的图的子图。不难发现剩下的路是没有环的（通过欧拉公式证明，略取），也就是一棵树，我们把这样的树叫做该图的生成树，而所有生成树中所有边的权值之和最小的树称之为该图的最小生成树，最小生成树有如下性质
最小生成树有
V个顶点(包含了图的所有顶点),V-1条边一个图最小生成树不唯一
下面就来说说最小生成树的算法实现
算法
prim算法
prim算法可以说很简单易懂，但自己的代码不忍直视，所以下面讲原理，代码就不贴了QAQ
prim算法的证明是图论问题，涉及的数学比较多，这里也不说了，主要看看实现步骤：
prim算法是子树一步一步扩展的过程，每经历一步，子树就多一条边，经过
v-1次后子树有v-1条边，此时算法结束；prim算法走的是贪心策略，每一步都寻找与自己相邻边中权值最小的边；