最小生成ツリーのPrimアルゴリズム

変換元:http://www.java3z.com/cwbwebhome/article/article19/res114.html
1、生成木の概念  連通図GのサブマップGのすべての頂点を含むツリーであれば、このサブマップをGの生成ツリーと呼ぶ.
生成ツリーは、連通図の極小連通サブ図である.極小とは、木に任意に1つのエッジを追加すると、1つの回路が現れることを意味します.エッジを1つ削除すると、非連通図になります.生成ツリーの各エッジの重み値の合計を生成ツリーの重みと呼びます.重みが最も小さい生成ツリーを最小生成ツリーと呼ぶ.
2、最小生成木の性質哲学的な観点から言えば、物事ごとに独自の性質があり、図の最小生成木も例外ではない.生成ツリーの定義によれば、n個の頂点の連通ネットワークの生成ツリーには、n個の頂点、n−1個のエッジがある.
3、最小生成ツリーを構築するには、(1).できるだけ重みの小さいエッジを選択するが、ループ(すなわちループ)を構成することはできないという2つの問題を解決する.(2).ネットワークのn個の頂点を接続するためにn−1個の適切なエッジを選択する.最小生成木を求めるアルゴリズムは一般に貪欲な戦略を用い,PrimアルゴリズムやKrusalアルゴリズムなどがある.
プリムアルゴリズムの基本思想:1)生成木を空にし、頂点を取って生成木に加える.2)一方の端点が生成ツリーにあり、他方の端点が生成ツリーのエッジにない場合、重みの最小のエッジを選択し、他方の端点と生成ツリーに追加します.3)すべての頂点が生成ツリーに入るまで手順2を繰り返し,そのときの生成ツリーが最小生成ツリーとなる.
すなわち、連通ネットワークN={V,E}のいずれかの頂点u 0から、それに関連付けられた最小重み値を有するエッジ(u 0,v)を選択し、その頂点vを生成ツリーの頂点集合Uに加える.その後、各ステップは、1つの頂点からUにあり、もう1つの頂点は、Uの各エッジにおいて重み値が最も小さいエッジ(u,v)を選択せず、その頂点vを集合Uに加える.このようにして、ネットワーク内のすべての頂点が生成ツリー頂点集合Uに加わるまで継続する.作成プログラム:次の重み付き無方向図に対して、ノードの個数とすべてのエッジ重み値を与え、Primアルゴリズムで最小生成ツリーを求める.コードの注釈は私が詳しく書いていて、理解しやすいので、いくつか説明しなければなりません.
(1)、2つのforループはいずれも2から始まる.通常、最初のノードを生成ツリーにデフォルトで追加するので、その後は再検索する必要はない.(2)、lowcost[i]は、ノードiを終点とする最小エッジ重み値を記録する.初期化時に最初のノードがデフォルトで生成ツリーに追加されるためlowcost[i]=graph[1][i]、すなわち最小エッジ重み値は各ノードから1番ノードまでのエッジ重み値の中で最小となる.(3)、mst[i]はlowcost[i]に対応する始点を記録しており、始点があり、終点があり、唯一1つのエッジを特定することができる.初期化時mst[i]=1,すなわち各エッジが1番ノードから出発する.入力データ:7 11 A B 7 A D 5 B C 8 B D 9 B E 7 C E 5 D E 15 D F 6 E F 8 E G 9 F 11
出力:A-D:5 D-F:6 A-B:7 B-E:7 E-C:5 E-G:9 Total:39最小生成ツリーPrimアルゴリズム素朴版java言語実装コードは以下の通りである

import java.util.*;
public class Main {  
 static int MAXCOST=Integer.MAX_VALUE;

 static int Prim(int graph[][], int n){
   /* lowcost[i]   i          ， lowcost[i]=0     i      */
   int lowcost[]=new int[n+1];
 
   /* mst[i]    lowcost[i]   ， mst[i]=0     i      */
   int mst[]=new int[n+1];
 
   int min, minid, sum = 0;
 
   /*     1        ， 2         */
    for (int i = 2; i <= n; i++){
	/*              1       */
	lowcost[i] = graph[1][i];
 
	/*               1    */
	mst[i] = 1;
     }
 
    /*   1         */
    mst[1] = 0;
 
    /* n       n-1          */
    for (int i = 2; i <= n; i++){
	min = MAXCOST;
	minid = 0;
 
       /*               minid */
       for (int j = 2; j <= n; j++){
	  /*              */
	  if (lowcost[j] < min && lowcost[j] != 0){
	     min = lowcost[j];
	     minid = j;
	  }
       }
     
       /*          :  ，  ，   */
	System.out.printf("%c - %c : %d
", mst[minid] + 'A' - 1, minid + 'A' - 1, min);
 
       /*      */
       sum += min;
 
       /*     minid      */
       lowcost[minid] = 0;
 
       /*       minid         */
       for (int j = 2; j <= n; j++){
         /*         */
	  if (graph[minid][j] < lowcost[j]){
	      /*        */
	      lowcost[j] = graph[minid][j];
 
	      /*            */
	      mst[j] = minid;
	   }
       }
     }
     /*         */
	return sum;
   }
 
  public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
    int  cost;
    char chx, chy;
 
    /*           */
    int n=sc.nextInt();//  
    int m=sc.nextInt();//  
    int graph[][]=new int[n+1][n+1];

    /*     ，            */
    for (int i = 1; i <= n; i++){
	for (int j = 1; j <= n; j++){
		graph[i][j] = MAXCOST;
	}
    }
 
    /*       */
    for (int k = 0; k < m; k++){
        chx=sc.next().charAt(0);
        chy=sc.next().charAt(0);
        cost=sc.nextInt();
	 int i = chx - 'A' + 1;
	 int j = chy - 'A' + 1;
	 graph[i][j] = cost;
	 graph[j][i] = cost;
     }
 
    /*         */
     cost = Prim(graph, n);
 
    /*         */
     System.out.println("Total:"+cost);
 
    }
}