primshort.java

用java实现了最小求解连通图的最小生成树问题

public class PrimShort {
	
	public static final int MAX = 1000;
	int[] vt = null;
	int[] v = null;
	int[][] edge = null;
	int[] dis = null;
	int r;
	int index = 1;
	
	public PrimShort(int[] v,int[][] edge,int[] dis,int r) {
		this.v  = v;
		this.edge = edge;
		this.dis = dis;
		this.r = r;
		vt = new int[v.length];
		vt[0] = r;
	}
	

	public static void main(String[] args) {
		
		int[] v = {0,1,2,3,4,5};
		int[] vt = new int[v.length];
		int[] dis = new int[v.length];
		int[][] edge = new int[v.length][v.length];
		edge[0][1]=10;
		edge[1][0]=10;
		edge[0][3] = 30;
		edge[0][4] = 45;
		edge[1][2] = 12;
		edge[1][4] = 40;
		edge[1][5] = 25;
		edge[2][4] = 35;
		edge[2][5] = 14;
		edge[3][4] = 16;
		edge[3][5] = 18;
		edge[4][5] = 50;
		for(int i=0;i<v.length;i++) 
			for(int j=0;j<v.length;j++) {
				if(edge[i][j] != 0) edge[i][j] = edge[j][i];
			}
 		
		for(int i=0;i<v.length;i++) 
			for(int j=0;j<v.length;j++) {
				if(edge[i][j] != 0) edge[i][j] = MAX;
			}
		
		PrimShort ps = new PrimShort(v,edge,dis,0);
		ps.primShort();
		
		
	}
	
	public boolean equals(int[] a,int[] b) {
		for(int i=0;i<a.length;i++) {
			if(a[i] != b[i]) {
				return false;
			}
		}
		return true;
	}
	
	public Mi min(int[] a) {
		Mi mi = null;
		int m = a[0];
		int j = 0;
		for(int i=1;i<a.length;i++) {
			if(m>a[i]) {
				m = a[i];
				j = i;
			}
		}
		mi = new Mi(m,j);
		return mi;
	}
	
	public boolean in(int[] a,int b) {
		for(int i=0;i<a.length;i++) {
			if(b == a[i]) return true;
		}
		return false;
	}
	
	public int[] minus(int[] a,int[] b){
		int[] c = new int[a.length-b.length];
		int j = 0;
		for(int i=0;i<b.length;i++) {
			if(!in(a,b[i])) {
				c[j] = b[i];
				j++;
			}
		}
		return c;
	}
	
	public void primShort() {
		vt[0] = r;
		dis[r] = 0;
		for(int k=0,i=v[0];i!=r&&k<v.length;k++) {
			if(edge[r][i]<MAX) dis[i] = edge[r][i];
			else dis[i] = MAX;
		}
		
		while(!equals(vt,v)) {
			Mi mi = null;
			int[] ve = minus(v,vt);
			mi = min(ve);
			int u = mi.i;
			dis[u] = mi.m;
			vt[index] = u;
			index ++;
			for(int i=0;i<ve.length;i++) {
				dis[ve[i]] = minmum(dis[ve[i]],edge[u][ve[i]]);
			}
				
		}
	}
	
	private class Mi {
		int m;
		int i;
		public Mi(int m,int i) {
			this.m = m;
			this.i = i;
		}
	}
	
	private int minmum(int a,int b) {
		return a<=b ? a:b;
	}
}