最小生成树算法源码 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 = new ArrayList（）;
	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 pqw;
		
		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; ++