java编写Kruskal算法实现最小生成树

Kruskal算法

算法思想很简单就是一个图中最短（权值最小）的那条边就是最小生成树中的边，但是若加上这条边后最小生成树中形成了“环”，则排除这条边继续找出剩下边中的最短边加入最小生成树。而判断是否形成了“环”则是通过并查集的isConnected方法来判断两点（这俩点已在最小生成树中）是否已相连，若已相连我再把这条边加入最小生成树中不就出现“环”了么！（关于并查集的isConnecte方法介绍请看我的另一篇博客）

实现代码:类KruskalMST

public class KruskalMST {
	
	private ArrayList<Edge> mst=new ArrayList<Edge>();  //存储最小生成树的Edge
	private int mstWeight;    //最小的权值和
	
	public KruskalMST(SparseGraph sg) {
		MinHeap mh=new MinHeap(sg.E());
		for(int i=0;i<sg.V();i++){
			ArrayList<Edge> arr=sg.getGraph(i);
			Iterator<Edge> ite=arr.iterator();
			while(ite.hasNext()){
				Edge ed=ite.next();
				if(ed.v()<ed.w()){   //防止插入重复边
					mh.insert(ed);
				}				
			}
		}
		
		UnionFind uf=new UnionFind(sg.V());     //通过并查集来检测是否出现"环"
		while(!mh.isEmpty()&&mst.size()<(sg.V()-1)){
			Edge e=mh.extractMin();
			if(uf.isConnected(e.v(), e.w())){
				continue;
			}
			mst.add(e);
			uf.unionElements(e.v(), e.w());  //将e.v()和e.w()合并
		}
		mstWeight=mst.get(0).wt();
		for(int i=1;i<mst.size();i++){
			mstWeight+=mst.get(i).wt();
		}
	}

	public ArrayList<Edge> mstEdges(){
		return mst;
	}
	
	public int result(){
		return mstWeight;
	}

}
           

比较Prim、LazyPrim、Kruskal算法的效率:

比较代码:

int N=30;  //顶点
		int M=200;   //边
		SparseGraph sg=new SparseGraph(N,false);
		for(int i=0;i<M;i++){
			sg.addEdge(new Random().nextInt(N), new Random().nextInt(N),new Random().nextInt(100)+1);//权值[1,101)
		}
		System.out.println("PrimMST耗时:");
		long startTime=System.nanoTime();   //获取开始时间
		PrimMST la=new PrimMST(sg);
		long endTime=System.nanoTime(); //获取结束时间  
		System.out.println("程序运行时间： "+(endTime-startTime)+" 纳秒"); 
		
		System.out.println("LazyPrimMST耗时:");
		long s_startTime=System.nanoTime();   //获取开始时间
		LazyPrimMST lpm=new LazyPrimMST(sg);
		long s_endTime=System.nanoTime(); //获取结束时间  
		System.out.println("程序运行时间： "+(s_endTime-s_startTime)+" 纳秒"); 

		
		System.out.println("KruskalMST耗时:");
		long t_startTime=System.nanoTime();   //获取开始时间
		KruskalMST km=new KruskalMST(sg);
		long t_endTime=System.nanoTime(); //获取结束时间  
		System.out.println("程序运行时间： "+(t_endTime-t_startTime)+" 纳秒"); 
           

比较结果

Kruskal算法实现起来比较简单，不过速度上大致还是比Prim算法慢一点的