POJ 1789最小生成ツリーのprimアルゴリズム

1、生成木
連通図Gのサブ図がGのすべての頂点を含むツリーである場合、このサブ図をGの生成ツリー(SpanningTree)と呼ぶ.
生成ツリーは、図中のすべての頂点を含む連通図であり、図の生成ツリーは唯一ではない.異なる頂点から遍歴し,異なる生成ツリーを得ることができる.
2、最小生成ツリー
連通する重み付きマップ(連通網)Gについても、その生成木は重み付きである.生成木Tの各辺の重み値の総和をその木の重みと呼び,重みの最小の生成木をGの最小生成木(MinimSpannirngTree)と呼ぶ.最小生成ツリーはMSTと略記することができる.
3、MST性質
N=(V,{E})は連通網であり,Uは頂点集合Vの非空子集合であると仮定する.(u,v)が最小値(代価)を有するエッジであり、uがUに属し、vがV−U(すなわち、U対立集合)に属する場合、エッジ(u,v)を含む最小生成ツリーが必ず存在する.
注意primとkruskalアルゴリズムはMSTの性質を利用している
Primアルゴリズムは最小生成ツリーの基本思想を求めます:
　　1.まず、開始点として1つの点を選択します.たとえば、1頂点をUセットに追加します.
    2.すべてのu∈U,v∈V−Uの辺(u,v)∈Eの中で,重みの最小の辺(u,v)を探し,この辺を集合Tに加え,この辺の非Uの頂点をUに加える.このステップの機能は、エッジセットEにおいて1つのエッジを探すことであり、このエッジは、まずエッジの2つの頂点がそれぞれ頂点セットUおよびV−Uにあり、次にエッジの重みが最小であるという条件を満たすことを要求する.このエッジを見つけたら、このエッジをエッジセットTに配置し、このエッジのUにない頂点をUに追加します.
3:U=Vの場合、アルゴリズムは終了する.そうでない場合は、手順2を繰り返します.本ステップはサイクル終了条件と見なすことができる.U=Vの場合,ステップ2でn−1回(nを図中の頂点の数とする)が実行され,TEにもn−1辺が追加され,このn−1辺が求められる最小生成木の辺であると算出できる.
例:POJ 1789
タイトル:n台のトラックのバーコード(7桁文字列)を与え、2台のトラック間の距離は2本のバーコードが同じ位置の文字と異なる個数であり、すべてのトラックを含む最小距離を求める.
Sample Input
4
aaaaaaa
baaaaaa
abaaaaa
aabaaaa
0
Sample Output
The highest possible quality is 1/3.
問題を解く:上記の関係に従って図を構築すると,ノードはトラックの番号,エッジの重み値はトラック間の距離となり,本問題を1つの図の最小生成木を求める問題に容易になる.

import java.util.Scanner;
import java.util.Arrays;
public class Main{
  private int n; //     
  private int G[][];//    
  String[] s;//n       

  public Main(int n,String s[]){
      this.n=n;
      this.s=s;
      G=new int[n+1][n+1];
      init();
     
   }

  private int getdis(String s,String t)/*              */
  { 
    int tmp=0; 
    for(int i=0;i<7;i++) 
    { 
        if(s.charAt(i)!=t.charAt(i)) tmp++; 
    } 
    return tmp; 
  } 
  
  public static void main(String args[]){
      Scanner in=new Scanner(System.in);
     while(true){
      int n=in.nextInt();
      if(n==0) break;
      String s[]=new String[n+1];
      for(int i=1;i<=n;i++)
         s[i]=in.next();
      Main m=new Main(n,s);
      System.out.println("The highest possible quality is 1/"+m.prim()+"."); 
     }


   }

    
  private void init(){/*             */ 
    for(int i=1;i<=n;i++){ 
        G[i][i]=Integer.MAX_VALUE; 
        for(int j=i+1;j<=n;j++) 
        { 
            int t=getdis(s[i],s[j]); 
            G[i][j]=G[j][i]=t; 
        } 
    } 
  } 

    public int prim(){
       int sum = 0;
       boolean flag[]=new boolean[n+1];
       flag[1] = true; //         U 
                 
       for(int k=1; k< n; k++){    //  n-1 ，  n-1  
         int min = Integer.MAX_VALUE,min_i = 1;
         for(int i=1; i<=n; i++){
           if( !flag[i] && G[1][i] < min){
            min = G[1][i];
            min_i = i;
           }
          }
                
        flag[min_i] = true; //
        for(int i=1; i<= n; i++){ 
          if( !flag[i] && G[1][i] > G[min_i][i]){
              G[1][i] = G[min_i][i];
          }               
       }
              
       sum += G[1][min_i];//    
     }          
            
    return sum;
            
  }
}

ソースのダウンロード: