摘要：
1，克鲁斯卡尔算法的介绍
2，克鲁斯卡尔算法的实现
1，克鲁斯卡尔算法的介绍
克鲁斯卡尔(Kruskal)算法和我们前面讲的《普里姆(Prim)算法》一样，也是求最小生成树的，它们使用的都是贪心的策略。不同的地方在于Prim算法是选择点，而Kruskal算法是选择边。
Kruskal算法的实现原理比较简单，首先要对图中的所有边进行排序，然后每次选择权值最小的边，但要保证选的边不能构成环路，一直选择下去，直到不能选择为止。所以Kruskal算法更适合计算稀疏图的最小生成树。
判断能不能构成环路我们可以使用《并查集》，就是判断边的两个点是否在同一个连通分量，如果在同一个连通分量，这条边就不能选，否则可以选，如图下图所示。
