testprim.java

贪心法的算法

package greedy;

public class TestPrim {
	
	public static void prim(int n,float[][] c) {
		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("("+closest[j]+","+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[][] c = new float[n+1][n+1];
		float max = Float.MAX_VALUE;
		for(int i = 0;i<=6;i++) {
			for(int j = 0;j<=6;j++) {
				c[i][j] = max;
			}
		}
	
		c[1][2] = 10;
		c[1][4] = 30;
		c[1][5] = 45;
		c[2][1] = 10;
		c[2][3] = 50;
		c[2][5] = 40;
		c[2][6] = 25;
		c[3][2] = 50;
		c[3][5] = 35;
		c[3][6] = 15;
		
		c[4][1] = 30;
		c[4][6] = 20;
		c[5][1] = 45;
		c[5][2] = 40;
		c[5][3] = 35;
		c[5][6] = 55;
		c[6][2] = 25;
		c[6][3] = 15;
		c[6][4] = 20;
		System.out.println("由Prim算法产生的最小生成树边的产生顺序如下：");
		prim(6,c);
	}
}