【算法导论】最小生成树

最小生成树就是在一个图中找到一条树，这些树可以包括图中所有的点并且这些 边权重的代价是最低的。如下图：

在本章中，我们将讨论两个最小生成树的算法：克鲁斯卡尔（Kruskal）算法和普利姆（Prim）算法，这两种算法均是使用贪心策略来完成最小生成树的生成，但是他们所使用的具体方式却有所不同。

1.Kruskal算法

Kruskal算法的核心是寻找当前图中权重最低的边，如果他们属于不同的集合则添加进最短路中（如下图第四行第二图，找到最小权重边7后并没有加入到最短路中去），最后将多生成森林组成成一棵树。

2.Prim算法

prim依然利用了贪心的思想，只不过他不在全局上找权重最低的边，而是不断的从当前集合出发，找当前集合中点的最短出度边，以此来构造最短生成树。