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算法慢一點的