prim.java

包括冒泡排序

/**
 * 用prim算法求图的最小生成树
 * @author jok
 * 2008/12/04
 * 
 */

package cn.com.csu.algorithm;

public class Prim {
  
  private float[] lowcost;
  private int[] closest;
  private boolean[] s;
  public void prim(int n,float[][] c) {
    lowcost = new float[n+1]; //lowcost[i]代表第i个点与前面生成的树的最小权值
    closest = new int[n+1]; //closest[i]代表i结点的前一个邻接点
    s = new boolean[n+1];//s[i]为true代表第i个结点被选中
    
    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++) {//循环n-1次，每次找出一个点加入生成树中
      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) {
    Prim p = new Prim();
    float max = Float.MAX_VALUE;
    float[][] c = {{max,max,max,max,max,max,max},{max,max,6,1,5,max,max},{max,6,max,5,max,3,max}
    ,{max,1,5,max,5,6,4},{max,5,max,5,max,max,2},{max,max,3,6,max,max,6},{max,max,max,4,2,6,max}};
    p.prim(6, c);
  }

}