克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用（所选的边不能构成回路）的最小权植边。所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考察每一条边（u，v）。 具体实现过程如下： <1>　设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T={V,空}，图中每个顶点自成一格连通分量。 <2>　在Ｅ中选择一条具有最小权植的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到Ｔ中；否则，即这条边的两个顶点落到同一连通分量 上，则将此边舍去（此后永不选用这条边），重新选择一条权植最小的边。 <3>　如此重复下去，直到所有顶点在同一连通分量上为止。

克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树 [1] 。

对给定的图结构，主体利用贪心算法实现求解最小生成树的Kruskal算法，其中每次查找权值最小的边用快速排序实现优化。每次在满足和已选边不构成回路的条件下选择一条权植最小的边，添加到新的生成树中。

对给定的图结构，用贪心算法思想实现求解最小生成树的Kruskal算法。每次在满足和已选边不构成回路的条件下选择一条权植最小的边，添加到新的生成数中。这是我们算法设计与分析的实验报告，大家可以下载参考。

项目介绍 使用查找无向加权图的（MST）的Java程序。 项目特色 以最有效的形式使用。 使用 通过命令行从输入文件中读取无向加权图。 输入文件包含以下内容（请参见testUF.txt）： 零个或多个以'c'开头的注释行 后面跟一个整数，代表图中的节点数 然后每行一条边。 一个整数三元组代表每个边缘，其中第三个整数是前两个整数之间的边缘权重。 也就是说，边缘1 2 3表示边缘1和2之间的权重为3。 将结果输出到文件（请参见testUFOutput.txt）。 输出文件由构成最小生成树的边以及MST的总权重组成。

从文件中Test类用来读取数据文件，可事先将数据输入文件中，Kruskal算法解决最小生成树