/*
*日期: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?			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?				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;?++