最小生成树：Kruskal（克鲁斯卡尔）算法实现(java)
算法描述：Kruskal（克鲁斯卡尔）算法需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系。
算法过程：
1.将图各边按照权值进行排序
2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。
3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。
import java.util.Scanner;import java.util.Arrays;public class KruskalTest{ private int father[]; private int son[]; private Edge e[]; private int n;//结点个数 private int l;//边的数目 public KruskalTest(int n,int l,Edge[] e){ this.n=n; this.l=l; this.e=e; father=new int[n]; son=new int[n]; for(int i = 0; i < n; ++i){ father[i] = i;//将每个顶点初始化为一个集合，父节点指向自己。 son[i]=1;//初始化每个父节点的儿子数为1 } } public static void main(String args[]){ Scanner scan = new Scanner(System.in); System.out.println("请输入测试次数:"); int ncase = scan.nextInt(); //测试次数 while((ncase--)!=0){ int n = scan.nextInt(); //图的顶点数 int l = scan.nextInt(); //图的边数 Edge[] e=new Edge[l]; for(int i = 0; i < l ; ++i){//输入边的数据 int a=scan.nextInt(); int b=scan.nextInt(); double weight=scan.nextDouble(); e[i]=new Edge(a,b,weight); } KruskalTest spt = new KruskalTest(n,l,e); System.out.println(spt.kruskal()); } } public int unionsearch(int x){ //查找根结点+路径压缩 return (x == father[x]) ? x : unionsearch(father[x]); } public boolean join(int x, int y){ //合并 int root1, root2; root1 = unionsearch(x); root2 = unionsearch(y); if(root1 == root2){ //为环 return false; } else if(son[root1] >= son[root2]){ father[root2] = root1; son[root1] += son[root2]; } else { father[root1] = root2; son[root2] += son[root1]; } return true; } public double kruskal(){ double sum=0; int ltotal=0; boolean flag=false; Arrays.sort(e); //按权值由小到大排序 for(int i = 0; i < l; ++i) { if(join(e[i].a, e[i].b)==true) { ltotal++; //边数加1 sum += e[i].weight; //记录权值之和 System.out.println(e[i].a+"-->"+e[i].b); } if(ltotal == n - 1) //最小生成树条件：边数=顶点数-1 { flag = true; break; } } if(flag) return sum; else{ System.out.println("此图没有最小生成树"); return -1; } } } class Edge implements Comparable { int a; //边的一个顶点，从数字0开始 int b; //边的另一个顶点 double weight; //权重 Edge(int a,int b,double weight){ this.a=a; this.b=b; this.weight=weight; } @Override public int compareTo(Object o){ Edge m = (Edge)o; int result=(int)(this.weight - m.weight); if(result>0) return 1; else if(result==0) return 0; else return -1; } }