最小生成树：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;    } }

运行：
C:\test>java KruskalTest
请输入测试次数:
2
5 8
0 1 2
1 4 9
1 2 8
4 3 7
3 0 10
0 2 12
2 3 6
2 4 3
0-->1
2-->4
2-->3
1-->2
19.0
7 9
0 1 28
1 2 16
2 3 12
0 5 10
4 3 22
4 6 24
4 5 25
1 6 14
3 6 18
0-->5
2-->3
1-->6
1-->2
4-->3
4-->5
99.0
下载源码：