Java实现最小生成树算法之Kruskal算法

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class mintree {
	public static int n;//结点数
	public static int m;//路径数
	public static int check[];
	public static int count=0;
	public static HashSet<node>set=new HashSet<node>();//存储已经访问过的路径信息
	public static node[]list=new node[515556];//存储路径信息，起点，终点，路径长
	
	public static int find(int x)//并查集中的并
	{
		return (check[x]==x)?x:(check[x]=find(check[x]));
	}
	public static void Kruskal()
	{
		set=new HashSet<node>();
		for(int i=0;i<list.length;i++)
		{
				if(find(list[i].start)!=find(list[i].end))
				{
					
					count++;
					set.add(list[i]);
					check[find(list[i].start)]=find(list[i].end);
					if(count==n-1)
						break;
				}
		}
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		check=new int [n];
		for(int i=0;i<n;i++)
			check[i]=i;
		list=new node[m];
		for(int i=0;i<m;i++)
		{
			int n1=sc.nextInt();
			int n2=sc.nextInt();
			int n3=sc.nextInt();
			node node1=new node(n1-1, n2-1, n3);
			list[i]=node1;
		}
		Arrays.sort(list);//将路径长从从小到大排序
		Kruskal();
		for(node value:set)
		{
			System.out.println((value.start+1)+"--->"+(value.end+1));
		}
		
	}
	static class node implements Comparable<node>//创建一个内部类并且实现Comparable接口，这样当使用Arrays.sort方法是就能直接排序了
	{
		int start;
		int end;
		int length;
		public node(int start,int end,int length)
		{
			this.start=start;
			this.end=end;
			this.length=length;
		}
		@Override
		public int compareTo(node o) {
			// TODO Auto-generated method stub
			return this.length-o.length;
		}
	}
}