edgenode.java

《算法设计与分析》王晓东编著

public class EdgeNode implements Comparable
{
	float weight;
	int u,v;
	
	EdgeNode(int uu,int vv,float ww)
	{
		u=uu;
		v=vv;
		weight=ww;
	}
	
	public int compareTo(Object x)
	{
		double xw=((EdgeNode)x).weight;
		if (weight<xw) return -1;
		if (weight==xw) return 0;
		return 1;
	}
	
	public static boolean kruskal(int n,int e,EdgeNode[] E,EdgeNode[] t)
	{
		MinHeap H=new MinHeap(1);
		H.initialize(E,e);
		FastUnionFind U=new FastUnionFind(n);
		int k=0;
		while (e>0 && k<n-1) {
			EdgeNode x=(EdgeNode)H.removeMin();			
			e--;
			int a=U.find(x.u);
			int b=U.find(x.v);
			if (a!=b) {
				t[k++]=x;
				U.union(a,b);
			}
		}
		return (k==n-1);
	}

	public static void main(String args[])
	{
		int n=6;		
		EdgeNode[] E=new EdgeNode[]{new EdgeNode(1,2,6),
				new EdgeNode(1,3,1),
				new EdgeNode(1,4,5),
				new EdgeNode(2,3,5),
				new EdgeNode(2,5,3),
				new EdgeNode(3,4,5),
				new EdgeNode(3,5,6),
				new EdgeNode(3,6,4),
				new EdgeNode(4,6,2),
				new EdgeNode(5,6,6)};
		
		EdgeNode[] t=new EdgeNode[n];
		
		if (kruskal(n,E.length,E,t))
		{
			for (int j=0;j<n-1;j++)
				System.out.println(t[j].u+" ,"+t[j].v);
		}
		else
			System.out.println("No answer.");
	}
}