一,kruskal算法简介

克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与prim算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树 。

二，实现步骤

部分流程图。

废话不多说，直接上代码，这张图请和代码一并观看，这样便于将图中的每一步找到对应的代码。 

要说的都写在了代码的注释里，请仔细思考并观看。

package TanXing;

public class MyKruskal {

    public static void main(String[] args) {
        //矩阵
        int [][]area = {
                {IM,23,IM,IM,IM,28,36},
                {23,IM,20,IM,IM,IM,1},
                {IM,20,IM,15,IM,IM,4},
                {IM,IM,15,IM,3,IM,9},
                {IM,IM,IM,3,IM,17,16},
                {28,IM,IM,IM,17,IM,25},
                {36,1,4,9,16,25,IM}
        };
        //顶点
        int []a = {1,2,3,4,5,6,7};
        MyKruskal myKruskal = new MyKruskal(a,area);
        myKruskal.kruskal();
    }
    //矩阵
    static int [][]area;
    //顶点
    static int []a;
    //定义一个不可到达量
    static int IM = Integer.MAX_VALUE;
    //边的条数
    static int route;

    //初始化
    MyKruskal(int []a,int [][]area){
        //保存顶点数
        int v = a.length;
        this.a = a;
        this.area = area;
        //请注意这里有个细节；这个初始化矩阵只要去看矩阵的上半或者下半
        //比如说有AB，但还有BA，而我们只需要去计算一条边
        for(int i = 0;i < v;i++){
            for(int j = i + 1;j < v;j++){
                if(area[i][j] != IM){
                    //计算好边的数量
                    route++;
                }
            }
        }
    }
    public void kruskal(){
        //保存最小生成树权值
        int sum = 0;
        int index = 0;
        //保存边的权和起始和终结点；
        int sourceEnd[]  =new int[route];
        //保存边
        IOC2 []ioc2s =getIOC();
        //保存最小生成树
        IOC2 []res = new IOC2[route];
        sortIOC(ioc2s);
        for(int i = 0;i < route;i++){
            int f1 = getPosition(ioc2s[i].startNode);
            int f2 = getPosition(ioc2s[i].endNode);
            //一个点的寻找终点
            int q1 = getEnd(sourceEnd,f1);
            int q2 = getEnd(sourceEnd,f2);
            //如果终结节点不同，就添加进sourceEnd
            //并且将边添加进最小生成树
            if(q1 != q2){
                sourceEnd[q1] = q2;
                res[index++] = ioc2s[i];
            }
        }
        for(int i = 0;i < index;i++){
            System.out.println(res[i]);
        }

    }
    //初始化IOC
    public IOC2[] getIOC(){
        int index = 0;
        IOC2 []bian = new IOC2[route];
        for(int i = 0;i < a.length;i++){
            for(int j = i + 1;j < a.length;j++){
                if(area[i][j] != IM){
                    bian[index++] = new IOC2(a[i],a[j],area[i][j]);
                }
            }
        }
        return bian;
    }
    //冒泡排序（这里不多讲）
    public void sortIOC(IOC2 []ioc2){
        for(int i = 0;i < route - 1;i++){
            for(int j = 0;j < route - i - 1;j++){
                if(ioc2[j].weight >ioc2[j + 1].weight){
                    IOC2 temp =null;
                    temp = ioc2[j + 1];
                    ioc2[j + 1] = ioc2[j];
                    ioc2[j] = temp;

                }
            }

        }
    }
    //获得这个点在序列表中的位置，比如说1节点，他在a[]序列表中的第0位
    public int getPosition(int num){
        for(int i = 0;i < a.length;i++){
            if(a[i] == num){
                return i;
            }
        }
        return -1;
    }
    //这里是整个kruskal算法的精华
    //寻找或者添加一个节点的根节点
    public int getEnd(int []sourceEnd,int p){
        while (sourceEnd[p] != 0){
            p = sourceEnd[p];
        }
        return p;

    }



}

class IOC2{
        int startNode;
        int endNode;
        int weight;

    public IOC2(int startNode, int endNode, int weight) {
        this.startNode = startNode;
        this.endNode = endNode;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "IOC2{" +
                "startNode=" + startNode +
                ", endNode=" + endNode +
                ", weight=" + weight +
                '}';
    }
}

算法不易，点个赞再走呗！感谢!