【数据结构与算法】最小生成树算法实现：Prim && Kruskal

Ⅰ. 最小生成树

​ 连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会形成一条回路。

若连通图由 n 个顶点组成，则其生成树必含 n 个顶点和 n-1 条边。因此构造最小生成树的准则有三条：

  1. 只能使用图中的边来构造最小生成树
  2. 只能使用恰好 n-1 条边来连接图中的 n 个顶点
  3. 选用的 n-1 条边不能构成回路

构造最小生成树的方法：Kruskal 算法和 Prim 算法。这两个算法都采用了逐步求解的贪心策略。

​ 贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解（也就是说这两种算法并不是万能的）。