kruskalalgorithm.java

本文件主要完成Kruskal算法。本文件包括三个类

import java.util.*;

class Vertice
{
	public char ch;
	
	public Vertice(char ch)
	{
		this.ch=ch;
	}
}

class Edge implements Comparable
{
	public char ch1;
	public  char ch2;
	public int weight;
	
	public Edge(char ch1,char ch2,int weight)
	{
		this.ch1=ch1;
		this.ch2=ch2;
		this.weight=weight;
	}
	
	public int compareTo(Object e)
	{
		return weight-((Edge)e).weight;
	}
	
	public String toString()
	{
		return "("+ch1+","+ch2+")";
	}
}

class Kruskal2
{
	Vector vector;
	Edge[] edgeVector;
	Vertice[] verticeVector;
	VerticeSet[] sets;
	
	public Kruskal2()
	{
		vector=new Vector();
		
		verticeVector=new Vertice[9];	
		verticeVector[0]=new Vertice('a');
		verticeVector[1]=new Vertice('b');
		verticeVector[2]=new Vertice('c');
		verticeVector[3]=new Vertice('d');
		verticeVector[4]=new Vertice('e');
		verticeVector[5]=new Vertice('f');	
		verticeVector[6]=new Vertice('g');
		verticeVector[7]=new Vertice('h');
		verticeVector[8]=new Vertice('i');	
		
		sets=new VerticeSet[verticeVector.length];
		for(int i=0;i<sets.length;i++)
			sets[i]=new VerticeSet(verticeVector[i].ch);
		
		
		edgeVector=new Edge[14];
		edgeVector[0]=new Edge('a','b',4);
		edgeVector[7]=new Edge('a','h',8);
		edgeVector[1]=new Edge('b','c',9);
		edgeVector[2]=new Edge('c','d',7);
		edgeVector[3]=new Edge('d','e',9);	
		edgeVector[4]=new Edge('e','f',10);
		edgeVector[5]=new Edge('g','f',2);
		edgeVector[6]=new Edge('h','g',1);

		edgeVector[8]=new Edge('b','h',11);
		edgeVector[9]=new Edge('h','i',7);
		edgeVector[10]=new Edge('i','g',6);
		edgeVector[11]=new Edge('c','i',2);
		edgeVector[12]=new Edge('c','f',4);
		edgeVector[13]=new Edge('d','f',14);
		
		Arrays.sort(edgeVector);
	}
	
	public void display()
	{
		for(int i=0;i<edgeVector.length;i++)
		{
			System.out.println("("+edgeVector[i].ch1+","+edgeVector[i].ch2+")="
					+edgeVector[i].weight);
		}
	}
	
	public void runWork()
	{
		for(int i=0;i<edgeVector.length;i++)
		{
			Edge e=edgeVector[i];
			char ch1=e.ch1;
			char ch2=e.ch2;
			
			char flag1=Find_Set(ch1);
			char flag2=Find_Set(ch2);
	
			if(flag1!=flag2)
			{
				vector.add(e);
				int index1=getSetIndex(flag1);
				int index2=getSetIndex(flag2);
				sets[index1].union(sets[index2]);
			}
		}
		
		System.out.println(vector.size());
	}
	
	public int getSetIndex(char flag)
	{
		for(int i=0;i<sets.length;i++)
			if(flag==sets[i].flag)
				return i;
		return 0;
	}
	
	public char Find_Set(char ch)
	{
		for(int i=0;i<sets.length;i++)
		{
			if(sets[i].active)
			{
				if(sets[i].search(ch))
					return sets[i].flag;
			}
		}
		
		return ' ';
	}
	
	public void printResult()
	{
		for(int i=0;i<vector.size();i++)
		{
			System.out.println((Edge)vector.get(i));
		}
	}
}

public class KruskalAlgorithm
{
	public static void main(String[] args)
	{
		Kruskal2 app=new Kruskal2();
		app.runWork();
		app.printResult();
	}	
}