最小生成树

• G = (V, E),若G的一个生成子图是一棵树，则称之为G的一棵生成树（记为T）
• 最小生成树：无向图G的所有生成树中，树枝的权值总和最小的称为G的最小生成树。
  
  常见的求解最小生成树的算法有\(Prim\)算法和\(Kruskal\)算法。显然，生成树是否存在和图是否连通是等价的，因此我们假设图是连通的。

最小生成树问题1（\(Prim\)算法）

\(Prim\)算法和\(Dijkstra\)算法相似，都是从某个顶点出发，不断添加边的算法。
首先，我们假设有一棵树只包含一个顶点\(v\)的树T，然后贪心地选取T和其他顶点之间相连的最小权值的边，并把它加到T中。不断进行这个操作，就可以得到一棵生成树。

• 考虑怎么证明这个方法得到的生成树就是最小生成树？
  纯理论证明看的头大，贪心懂得都懂。。。
• 如果每次都遍历未包含在生成树里面的点，复杂度高，所有和Dijkstra算法一样，考虑堆优化。