java實現最小生成樹的prim算法和kruskal算法

在邊賦權圖中，權值總和最小的生成樹稱為最小生成樹。構造最小生成樹有兩種算法，分別是prim算法和kruskal算法。在邊賦權圖中，如下圖所示:

在上述賦權圖中，可以看到圖的頂點編號和頂點之間鄰接邊的權值，若要以上圖來構建最小生成樹。結果應該如下所示:

這樣構建的最小生成樹的權值總和最小，為17

在構建最小生成樹中，一般有兩種算法，prim算法和kruskal算法

在prim算法中，通過加入最小鄰接邊的方法來建立最小生成樹算法。首先構造一個零圖，在選一個初始頂點加入到新集合中，然后分別在原先的頂點集合中抽取一個頂點，使得構成的邊為權值最小，然后將該筆邊加入到圖中，并將抽出的頂點加入到新集合中，重復這個過程，知道新集合等于原先的集合。

代碼如下:

package 最小生成樹;
/*
 * 最小生成樹prim算法，加入最小鄰接邊生成最小生成樹。
 * 首先構造一個零圖，選擇一個初始點加入到集合中，
 * 然后分別從原來頂點的集合中抽取一個頂點，
 * 選擇的標準是構造成的樹的權值最小，
 * 循序漸進最終生成一棵最小生成樹
 */
public class prim {
 /**
  * @author 劉雁冰
  * @date 2015-02-13 20:23
  */
 
 /*
  * m:定義為無法到達的距離
  * weight:鄰接矩陣表,weight表示權值
  * verNum:頂點的個數
  * lowerW:到新集合的最小權值
  * edge:存儲到新集合的邊
  * checked:判定頂點是否被抽取的集合
  */
 
 static int m=Integer.MAX_VALUE;
 static int[][] weight={
   {0, 0, 0, 0, 0, 0},  
   {0, m, 6, 9, 5, 13},  
   {0, 6, m, 6,7,8},  
   {0, 9,6,m,9,3},  
   {0, 5,7,9,m,3},  
   {0,13,8,3,3,m}  
 };
 static int verNum=weight.length;
 static int []lowerW=new int[verNum];
 static int []edge=new int[verNum];
 static boolean []checked=new boolean[verNum];
 
 public void prim(int n,int [][]w){
  checked[1]=true;            //抽取第一個頂點
  
  for(int i=1;i<=n;i++){          //初始化頂點集合
   lowerW[i]=w[1][i];
   edge[i]=1;
   checked[i]=false;
  }
  
  for(int i=1;i<=n;i++){
   int min=Integer.MAX_VALUE;
   int j=1;
   for(int k=2;k<=n;k++){        //判定是否抽取該頂點
    if(lowerW[k]<min&&(!checked[k])){
     min=lowerW[k];
     j=k;
    }
   }
   if(i<n)                //避免輸出第一個頂點到第一個頂點的情況
   System.out.println(j+"-->"+edge[j]);
   
   checked[j]=true;           //將頂點加入到新集合中
   
   for(int k=2;k<=n;k++){        //根據新加入的頂點，求得最小的權值
    if((w[j][k]<lowerW[k])&&(!checked[k])){
     lowerW[k]=weight[j][k];
     edge[k]=j;
    }
   }
  }
 }
 
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  prim p=new prim();
  p.prim(verNum-1,weight);
 }
}

測試結果如下:

在kruskal算法中，根據邊的權值以遞增的方式逐漸建立最小生成樹。具體操作是:將賦權圖每個頂點都看做森林，然后將圖中每條鄰接邊的權值按照升序的方式進行排列，接著從排列好的鄰接邊表中抽取權值最小的邊，寫入該邊的起始頂點和結束頂點，連接頂點將森林構成樹，然后讀取起始結束頂點的鄰接邊，優先抽取權值小的鄰接邊，繼續連接頂點將森林構成樹。添加鄰接邊的要求是加入到圖中的鄰接邊不構成回路。如此反復進行，直到已經添加n-1條邊為止。

代碼如下:

package 最小生成樹;
import java.util.ArrayList;
import java.util.Scanner;
/*
 * 最小生成樹kruskal算法：首先將每個頂點作為一棵森林，升序比較該頂點的鄰接邊，
 * 每次取最小權值的鄰接邊，將該鄰接邊連接的頂點與原先頂點構成一棵樹，接著尋找
 * 下一個頂點，繼續按照鄰接邊權值升序進行比較，取權值最小的構成樹...
 * 
 * 該類用一個Edge類構成一個鄰接邊的信息，包括鄰接邊的起始頂點與結束頂點，權值。
 * 用類Edge創建對象，錄入對象信息，按照對象的權值進行比較，符合條件的對象加入
 * 到鏈表中，最終按照鏈表順序輸出最小生成樹。
 */
public class kruskal {
 /**
  * @author 劉雁冰
  * @date 2015-02-13 20:23
  */
 
 /*
  * Max:定義頂點數組的最大值
  * edge:鏈表edge，存儲構造的Edge對象
  * target:鏈表trget,存儲最終得到結果的Edge對象
  * parent:存儲頂點信息的數組
  * n:頂點數
  */
 int Max=100;
 ArrayList<Edge>edge=new ArrayList<Edge>();
 ArrayList<Edge>target=new ArrayList<Edge>();
 int[] parent=new int[Max];
 Float TheMax=Float.MAX_VALUE;
 int n;
 
 public void init(){
  /**
   * p:起始頂點
   * q:結束頂點
   * w:邊的權值
   * n:頂點個數
   */
  Scanner scan =new Scanner(System.in);
  int p,q;
  double w;
  System.out.println("請輸入結點的個數:");
  n=scan.nextInt();
  System.out.println("按照'A,B,C'的格式輸入邊與邊的信息,ABC分別代表邊的起始頂點，結束頂點，權值(輸入-1 -1 -1結束輸入):");
  while(true){
   p=scan.nextInt();
   q=scan.nextInt();
   w=scan.nextDouble();
   if(p<0||q<0||w<0)break;
   Edge e=new Edge();
   e.start=p;
   e.end=q;
   e.weight=w;
   edge.add(e);
  }
  for(int i=1;i<=n;++i){          //初始化邊的信息數組
   parent[i]=i;
  }
 }
 
 /*
  * 對象合并，將上一對象的結束邊作為下一對象的起始邊
  */
 public void union(int j,int k){
  for(int i=1;i<=n;++i){
   if(parent[i]==j)
    parent[i]=k;
  }
 }
 
 public void kruskal(){
  int i=0;                 //頂點
  while(i<n-1&&edge.size()>0){       //如果只有一條邊或者沒有邊跳出
   double min=Double.MAX_VALUE;
   Edge temp=null; 
   for(int j=0;j<edge.size();++j){      //遍歷圖形
    Edge tt=edge.get(j);
    if(tt.weight<min){           //若兩個頂點有權值，即相連
    min=tt.weight;     
    temp=tt;
    }
  }
  
  //構造一棵樹
  int jj=parent[temp.start];
  int kk=parent[temp.end];
  
  
  if(jj!=kk){
   ++i;                 //以end作為下一條邊的start,尋找下一條邊
   target.add(temp);           //將找到的邊放入目標集合中
   union(jj,kk);             
  }
  edge.remove(temp);           //將臨時邊刪除
  }
  System.out.println("最小生成樹的路徑是:");
  for(int k=0;k<target.size();++k){     //輸出最小生成樹
   Edge e=target.get(k);
   System.out.println(e.start+"-->"+e.end);
  }
 }
 
 public static void main(String[] args) {
  // TODO Auto-generated method stub
   kruskal kr=new  kruskal();
   kr.init();
   kr.kruskal();
 }
}
/*
 * start:起始頂點
 * end:結束頂點
 * weight:權值
 */
class Edge{
 public int start;
 public int end;
 public double weight;
}

調試結果如下: