prim.java

《算法设计与分析》王晓东编著

public class Prim {
	public static void prim(int n,float[][] c)
	{// prim算法
		float[] lowcost=new float[n+1];
		int [] closest =new int[n+1];
		boolean [] s=new boolean[n+1];
		
		s[1]=true;
		for (int i=2;i<=n;i++) {
			lowcost[i]=c[1][i];
			closest[i]=1;
			s[i]=false;
		}
		
		for (int i=1;i<n;i++) {
			float min=Float.MAX_VALUE;
			int j=1;
			for (int k=2;k<=n;k++)
				if ((lowcost[k]<min) && (!s[k])) {
					min=lowcost[k];
					j=k;
				}
			System.out.println(j+", "+closest[j]);
			s[j]=true;
			for (int k=2;k<=n;k++)
				if ((c[j][k]<lowcost[k])&&(!s[k])) {
					lowcost[k]=c[j][k];
					closest[k]=j;
				}
		}
	}
	
	public static void main(String args[])
	{
		int n=6;
		float max=Float.MAX_VALUE;
		float[][] c=new float[][]{{0,0,0,0,0,0,0},
				          {0,max,6,1,5,max,max},
				          {0,6,max,5,max,3,max},
				          {0,1,5,max,5,6,4},
				          {0,5,max,5,max,max,2},
				          {0,max,3,6,max,max,6},
				          {0,max,max,4,2,6,max}};
		
		prim(n,c);
		                       
	}

}