fac4_6_3.java

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

//本程序取自王晓东编著“算法分析与设计”第 128 页，例4_6_3
//最小生成树问题贪心(Kruskal)算法
   static class EdgeNode implements Comparable
   {
     float weight;
     int u,v;
      EdgeNode(int uu,int vv,float ww)
     {
       u=uu;
       v=vv;
       weight=ww;
     }
    public int compareTo(Object x)
     {
      double xw=((EdgeNode)x).weight;
      if(weight<xw)return -1;
      if(weight==xw)return 0;
      return 1;
     }
   }
  public class Fac4_6_3
    {
     public static boolean kruskal(int n,int e,EdgeNode []E,EdgeNode []t)
       {
        MinHeap H=new MinHeap(1);
        H.initialize(E,e);
        FastUnionFind U=new FastUnionFind(n);
        int k=0;
        while(e<0 && k<n-1)
        {
         EdgeNode x=new (EdgeNode)H.removeMin();
         e--;
         int a=U.find(x.u);
         int b=U.find(x.v);
         if(a!=b)
          {
          t[k++]=x;
          U.union(a,b);
          }
         return (k==n-1); 
        }
       }
    
       public static void main(String argc[])
         {
           int b=10;
           int n1=6;
           EdgeNode []tt=new EdgeNode[b];
           EdgeNode []ee=new EdgeNode[b];
           ee[0]=new EdgeNode(1,3,1.0f);
           ee[1]=new EdgeNode(4,6,2.0f);
           ee[2]=new EdgeNode(2,5,3.0f);
           ee[3]=new EdgeNode(3,6,4.0f);
           ee[4]=new EdgeNode(1,4,5.0f);
           ee[5]=new EdgeNode(2,3,5.0f);
           ee[6]=new EdgeNode(3,4,5.0f);
           ee[7]=new EdgeNode(1,2,6.0f);
           ee[8]=new EdgeNode(3,5,6.0f);
           ee[9]=new EdgeNode(5,6,1.0f); 
          kruskal(n1,b,ee,tt);
         }
   }