主要思想

按照边的权重顺序(从小到大)处理它们，将边加入到最小生成树中，加入的边不会和已经加入的边构成环，直到树中V-1条边为止，这些一开始并不一定是互相连接的，但是后面会慢慢逐渐由一片森林组成一颗树，也就是图的最小生成树

定理： Kruskal算法能够计算任意加权连通图的最小生成树
证明： 因为下一条被加入的边不会与最小生成树中已经存在的边构成环，那么它就跨越了和树中顶点相邻的顶点组成的集合的补集所构成的一个切分。因为加入的这条边不会构成果环、它是目前唯一已知的横切边切是按照权重选择的边，所以它必然是最小的横切边。 因此，该算法能够连续选择权重最小的横切边。

实现

Prim算法是一条边一条边的来构造最小生成树，每一步都为一颗树添加一条边；Kruskal算法也是一条一条边的构造，但是在构造的时候它寻找的边会连接一片森林中的两棵树。 我们从一片由V颗顶点组成的森林中不断用可以找到的最小的边将两棵树合并，直到只剩下一棵树，它就是最小生成树
简单的说就是两个步骤：
将边按权重排序，然后再逐渐找出合适的边

public class KruskallMST {
     
	private Queue<Edge> mst;
	
	public KruskallMST(EdgeWeightGraph G) {
		mst = new LinkedList<Edge>();
		MinPQ<Edge> pq = new MinPQ<Edge>();
		for(Edge e:G.edges()) {
			
			pq.insert(e);
		}
		QuickUnion uf = new QuickUnion(G.V());
		
		while(!pq.isEmpty()&&mst.size()<G.V()-1) {
			Edge e = pq.delMin();
			System.out.println("删除最小节点"+e);
			int v = e.either(),w = e.other(v);
			if(uf.connected(v, w))
				continue;
			uf.union(v, w);
			System.out.println("添加边："+e);
			mst.add(e);
		}
	}
	
	public Iterable<Edge> edges(){
		return mst;
	}
}

测试

public class Test {
	public static void main(String[] args) {
		EdgeWeightGraph graph = new EdgeWeightGraph(8);

		graph.addEdge(new Edge(4, 5, 0.35));
		graph.addEdge(new Edge(4, 7, 0.37));
		graph.addEdge(new Edge(5, 7, 0.28));
		graph.addEdge(new Edge(0, 7, 0.16));
		graph.addEdge(new Edge(1, 5, 0.32));
		graph.addEdge(new Edge(0, 4, 0.38));
		graph.addEdge(new Edge(2, 3, 0.17));
		graph.addEdge(new Edge(1, 7, 0.19));
		graph.addEdge(new Edge(0, 2, 0.26));
		graph.addEdge(new Edge(1, 2, 0.36));
		graph.addEdge(new Edge(1, 3, 0.29));
		graph.addEdge(new Edge(2, 7, 0.34));
		graph.addEdge(new Edge(6, 2, 0.40));
		graph.addEdge(new Edge(3, 6, 0.52));
		graph.addEdge(new Edge(6, 0, 0.58));
		graph.addEdge(new Edge(6, 4, 0.93));

		Queue<Edge> q = new LinkedList<Edge>();
		KruskallMST km = new KruskallMST(graph);
		q = (Queue<Edge>) km.edges();
		System.out.println("最小生成树：");
		for (Edge edge : q) {
			System.out.println(edge);
		}
	}
}

结果

最小生成树：
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.40

实际Kruskal算法比Prim算法要慢一点，因为它在处理两个算法都要完成的优先队列之外还要进行connect()操作