kruskal.java

适于java初学者看的Kruskal算法

/**
 * @(#)Kruskal.java
 *
 *
 * @author 
 * @version 1.00 2007/4/29
 */


public class Kruskal {
	private int[][] List_Graph;
    private int[] Label;//每个边的标识
    private int[] Weight;
    private int[] Index_1;
    private int[] Index_2;
    private String Result;

    public Kruskal() {
      List_Graph = new int[][]
     {{0,1,4,9},
      {1,0,4,2},
      {4,4,0,5},
      {9,2,5,0}
      };//初始化graphic中点和点的距离，32767表示距离无穷大
      Label = new int[List_Graph.length];//List_Graph.length第一维数组长度4
      for(int i = 0; i < Label.length; i++)//初始化标记
     {
      Label[i] = i;
     }
     int j = (int)(Label.length + 1)*Label.length/2;//j=10
     Weight = new int[j];//用于存储待排序边的权值，数组长度m＝（n+1）*n*0.5,其中节点个数为n
     Index_1 = new int[j];//用于存储边的两个节点
     Index_2 = new int[j];
     Result = "最小生成树的边是："+"\n";//记录最小生成树的边
    }
    
     public String Get_Result()//获得变量Result
    {
     return Result;
    }
    
    //把边按权排序,graphic是List_Graphic
     public  int[] sort()
    {
     int[] a;
     int index = 0;
     for(int i = 0; i < Label.length; i++)
     for(int j = i+1; j < Label.length; j++)
     {
      if(List_Graph[i][j] < 32767)
     {
     Weight[index] = List_Graph[i][j];
     Index_1[index] = i;
     Index_2[index] = j;
     index = index + 1;
     }
       }
     a = new int[index - 1];
     a = Address_Sort(Weight,Weight.length);
     return a; 
    }
    
    public int[] Address_Sort(int[] a,int n)//地址排序
    {
    int[] Res = new int[n];//表示地址
    for(int i = 0 ; i < n; i++)
    {
     Res[i]  = i;
    }
    int t;
    int k;
    for(int j = 0 ; j < n-1; j++)
    {
     for(int i = 0 ; i < n-j-1; i++)
     {
      if(a[i] >= a[i+1])
      {
       k = a[i];
       a[i] = a[i+1];
       a[i+1] = k;
       t = Res[i];
       Res[i] = Res[i+1];
       Res[i+1] = t;//地址转换
       }
      }
     }
     return Res;
    }
    
    public void Min_Tree()//求最小生成树
    {
     int[] tag = new int[Weight.length];
     tag = sort();
     int i = 0;
     while(!Judge(Label))//Judge函数判断标记是否都是0
     {
      if(Label[Index_1[tag[i]]] != Label[Index_2[tag[i]]])//不是同一个点
      {
       Result = Result + Index_1[tag[i]] +"---"+ Index_2[tag[i]] + "\n";
       if(Label[Index_1[tag[i]]] < Label[Index_2[tag[i]]])
       {
        for(int k = 0; k < Label.length; k++)
        {
        if(Label[k] == Label[Index_2[tag[i]]])
         {
          Label[k] = Label[Index_1[tag[i]]];
         }
        }
        }
       else
      {
       for(int k = 0; k < Label.length; k++)
        {
         if(Label[k] == Label[Index_1[tag[i]]])
         {
          Label[k] = Label[Index_2[tag[i]]];
         }
        }
       }
      }
      else
      {
       i = i + 1;
      }
     }
   }
   
   public boolean Judge(int[] a)//判断标记是否都是0
   {
    for(int i = 0 ;i < a.length ; i++)
    {
     if(a[i] != 0)
     {
      return false;
     }
    }
    return true;
   }
   
   public static void main(String[] args) //主函数
   {
    Kruskal CK = new Kruskal();
    CK.Min_Tree();
    System.out.println(CK.Get_Result());
   }    
}