×îСÉú³ÉÊ÷ PrimËã·¨ java´úÂëʵÏÖ

 /*
*ÈÕÆÚ:2010-04-18 11:37
*¿ª·¢Õß:heroyan
*ÁªÏµ·½Ê½:zndxysf@126.com
*¹¦ÄÜ:ÎÞÏòͼ×îСÉú³ÉÊ÷PrimË㷨ʵÏÖ°¸Àý
*/
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class SpanningTree{
private static int MAX = 100;
private double cost[][] = new double[MAX][MAX];
private ArrayList<Edge> edge = new ArrayList<Edge>();
private int[] near = new int[MAX];
private static double INFINITY = 99999999.99;//¶¨ÒåÎÞÇî´ó
private double mincost = 0.0;//×îС³É±¾
private int n;//½áµã¸öÊý

public SpanningTree(){}

public static void main(String args[]){
SpanningTree sp = new SpanningTree();
sp.init();
sp.prim();
sp.print();
}
//³õʼ»¯
public void init(){
Scanner scan = new Scanner(System.in);
int p,q,w;

System.out.println("spanning tree begin!Input the node number:");
n = scan.nextInt();
//¶þάÊý×éµÄÌî³äҪעÒâ
for(int i = 0; i < MAX; ++i){
Arrays.fill(cost[i],INFINITY);
}
System.out.println("Input the graph(-1,-1,-1 to exit)");

while(true){
p = scan.nextInt();
q = scan.nextInt();
w = scan.nextInt();
if(p < 0 || q < 0 || w < 0){
break;
}
cost[p][q] = w;
cost[q][p] = w;
}

Edge tmp = getMinCostEdge();
edge.add(tmp);
p = tmp.start;
q = tmp.end;
mincost = cost[p][q];

for(int i = 1; i <= n; ++i){
if(cost[i][p] < cost[i][q]){
near[i] = p;
}else{
near[i] = q;
}
}
near[p] = near[q] = 0;
}
//Ñ°ÕÒ×îС³É±¾µÄ±ß
public Edge getMinCostEdge(){
Edge tmp = new Edge();
double min = INFINITY;

for(int i = 1; i < n; ++i){
for(int j = i+1; j <= n; ++j){
if(cost[i][j] < min){
min = cost[i][j];
tmp.start = i;
tmp.end = j;
}
}
}
//System.out.println(min);
return tmp;
}
//primËã·¨Ö÷Ìå
public void prim(){
//ÕÒʣϵÄn-2Ìõ±ß
for(int i = 2; i < n; ++i){
double min = INFINITY;
Edge