fac4_6_2.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 126 页，例
//最小生成树问题贪心(Prim)算法
   public class Fac4_6_2
 {
     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(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 argc[])
         {
           final float ff=Float.MAX_VALUE;
           int n1=6;
           float [][]c1={{0.0f,0.0f,0.0f,0.0f,0.0f,0.0f,0.0f},
                         {0.0f,0.0f,6.0f,1.0f,5.0f,ff,ff},
                         {0.0f,6.0f,0.0f,5.0f,ff,3.0f,ff},
                         {0.0f,1.0f,5.0f,0.0f,5.0f,6.0f,4.0f},
                         {0.0f,5.0f,ff,5.0f,0.0f,ff,2.0f},
                         {0.0f,ff,3.0f,6.0f,ff,0.0f,6.0f},
                         {0.0f,ff,ff,4.0f,2.0f,6.0f,0.0f}};
                        
          prim(n1,c1);
         }
   }