最近做大题目主要运用的都是数据结构方面的题，既有之前的最短路径的相关的算法，也有现在的最小生成树，这里先讲解Kruskal算法，主要是我先在刚会这个，prim算法，明天再看。
Kruskal算法算法其实和之前的djs算法有点类似，主要还是每次循环找出局部最优解，也就是最小权重的那条路，一次寻找即可，这里作者一开始俊德实现起来并不麻烦，但之后发现，循环找出最优解不是最麻烦的，大不了每次排序，就行了，但是之后发现最难的一块是不能出现环，举个例子，
如果只是单纯的按照权重来选择，肯定是这样选择的1—>2,1—>4,2—>4，这样的话会出现两个问题，第一个就是出现了环即1—>2—>4—>1这样显然是不行的，第二问题就是，这样选择出来的点事不全的，缺少了3这个点，所以选择路径的时候不仅是要看权重，还应该看选择的路径是否会构成环这种不允许出现的情况，其实重点就是这里，为了防止出现这种情况，我们又需要了解并查集这个概念，就是简单的如果两个数是一类的，那么我们就将它们合并，否则就不动，这就是并的操作，之后就是查，通过不断的向前查询，直到查询到该节点的根节点，之后用过比较两者的根节点是否相等来判断是否能够成一个环。
接下来就是最简单的最小生成树以及并查集的代码了：
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; } } }
作者很菜，如有不足，请指教。
