kruskal.java

用Java实现Kruskal算法 很详细

import java.util.*;
import java.io.*;

public class Kruskal {

	/**
	 * @param args
	 */
	static int LIMIT = 500;                  //边的个数
	
	public static void main(String[] args) {
		// TODO 自动生成方法存根
		String tempStr = new String("");           //临时String
		int mgSize = 0;								//图的大小
		int[][] mg = new int[100][100];			//图的邻接矩阵
		int i, j, k = 0;
		Edge [] edge;
		int forest[] = new int[LIMIT];				//并查集
		edge = new Edge[LIMIT];						//所有的边
		for( i = 0; i < LIMIT; i ++ )			//initialize 
			{
				edge[i] = new Edge();
				forest[i] = -1;
			}
		
		System.out.println( "Please input the size of your graph:");          //
		try
		{
		BufferedReader bufferedReader = new BufferedReader( new InputStreamReader( System.in ) );
		tempStr = bufferedReader.readLine(); 
		mgSize = Integer.parseInt( tempStr );
		} catch( IOException e ){}
		
		System.out.println( "Please input your graph:");         //
		Scanner scanner = new Scanner( System.in );
		for( i = 0; i < mgSize; i ++ )
			for( j = 0; j < mgSize; j ++ )
			{
				mg[i][j] = scanner.nextInt();
				if( mg[i][j] != 0 ) 
				{
					edge[k++].setEdge( i,j,mg[i][j]);
				}
			}
		
		for( i = 0; i < mgSize - 2; i ++ )           //未优化的冒泡
			for( j = 0; j < mgSize - i - 1; j ++ )
			{
				if( edge[j].w > edge[j+1].w )
					edge[j].swap( edge[j+1] );
			}
		
		k = 0;
		while( k < mgSize )                      //未优化的并查方法
		{
			int root1 = edge[k].v1;
			int root2 = edge[k].v2;
			while( forest[root1] >= 0 )
				root1 = forest[root1];
			while( forest[root2] >= 0 )
				root2 = forest[root2];
			if( root1 == root2 )
				k++;
			else
				{
					forest[root1] = root2;
					System.out.printf( "%d -- %d: %4d\n", root1, root2, edge[k++].w );
				}
		}
		
		
	}

}
class Edge					//边的结构
{
	int v1, v2, w;
	Edge(){ v1 = 0; v2 = 0; w = 0; }
	void setEdge( int  v1, int v2, int w )
	{
		this.v1 = v1; this.v2 = v2; this.w = w;
	}
	void swap( Edge b )
	{
		Edge temp = new Edge();
		temp.v1 = this.v1; temp.v2 = this.v2; temp.w = this.w;
		this.v1 = b.v1; this.v2 = b.v2; this.w = b.w;
		b.v1 = temp.v1; b.v2 = temp.v2; b.w = temp.w;
	}
}