package org.loda.graph;import org.loda.structure.MinQ;import org.loda.structure.Queue;import org.loda.util.In;/** * * @ClassName: KruskalMST * @Description:Kruskal最小生成树算法 * @author minjun* @date 2015年5月25日 下午10:50:01 * */public class KruskalMST { private Queue mst; private double weight; public KruskalMST(WeightGraph g){ int v=g.v(); mst=new Queue (); MinQ q=new MinQ (); UF uf=new UF(v); //将所有边添加到优先队列中 for(Edge edge:g.edges()){ q.offer(edge); } while(!q.isEmpty()){ Edge edge=q.poll(); int a=edge.oneSide(); int b=edge.otherSide(a); //如果已经连通，说明这条边无法继续加入，否则会形成环路 if(uf.connected(a, b)) continue; //将两个连通分量连通 uf.union(a, b); mst.enqueue(edge); weight+=edge.weight(); } } /** * * @Title: edges * @Description: 最小生成树的所有边 * @param @return 设定文件 * @return Iterable 返回类型 * @throws */ public Iterable edges(){ return mst; } /** * * @Title: weight * @Description: 最小生成树的权重 * @param @return 设定文件 * @return double 返回类型 * @throws */ public double weight(){ return weight; } public static void main(String[] args) { In in = new In("F:\\算法\\attach\\tinyEWG.txt"); WeightGraph g = new WeightGraph(in); KruskalMST m = new KruskalMST(g); for (Edge e : m.edges()) { System.out.println("边:"+e); } System.out.println(m.weight()); }} 所依赖的数据结构和前一篇的Prim算法相同，都是带权重边的无向图，和一条权重边，不过由于Kruskal算法的核心思想是不断找到最小的边，并查看他们连通与否，如果不连通，则合并他们成同一个连通分量，并将这条边加入到最小生成树。需要检测无向图的连通性，则需要利用到另外一个算法union-find并查集，下面给出并查集的简单实现
package org.loda.graph;/** * * @ClassName: UF * @Description:并查集 * @author minjun* @date 2015年5月25日 下午11:41:16 * */public class UF { //每个元素的标识 private int[] id; //连通分量数量 private int count; public UF(int n){ id=new int[n]; //初始化为n个不相连的点（连通分量）的值 count=n; for(int i=0;i
输入的测试数据为：
8
16 4 5 0.35 4 7 0.37 5 7 0.28 0 7 0.16 1 5 0.32 0 4 0.38 2 3 0.17 1 7 0.19 0 2 0.26 1 2 0.36 1 3 0.29 2 7 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93输出结果为 ：
边:0-7 0.16边:2-3 0.17边:1-7 0.19边:0-2 0.26边:5-7 0.28边:4-5 0.35边:6-2 0.41.81