克鲁斯卡尔算法形成最小生成树

package kruscal;

import java.util.Arrays;

public class KruscalCase {

    private int edgeNum; //边的个数
    private char[] vertex;  //顶点数组
    private int[][] matrix; //邻接矩阵
    //设置INF，表示两个节点不能连通
    private static final int INF=Integer.MAX_VALUE;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        char[] vertex= {'A','B','C','D','E','F','G'};
        int matrix[][]= {
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };

        //创建KruskcalCase实例对象
        KruscalCase kruscalCase=new KruscalCase(vertex,matrix);
        //输出构建的
        kruscalCase.print();
        kruscalCase.kruskal();

    }

    //构造器
    public  KruscalCase(char[] vertex,int[][] matrix) {
        //初始化顶点数和边的个数
        int vlen=vertex.length;

        //初始化顶点，this.vertex=vertex;
        //这里采用复制的方式
        this.vertex=new char[vlen];
        for(int i=0;i<vertex.length;i++) {
            this.vertex[i]=vertex[i];
        }

        //初始化边，可采用this.matrix=matrix;
        //这里同样采用复制
        this.matrix=new int[vlen][vlen];
        for(int i=0;i<vertex.length;i++) {
            for(int j=0;j<vertex.length;j++) {
                this.matrix[i][j]=matrix[i][j];
            }
        }

        //统计边的条数
        for(int i=0;i<vlen;i++) {
            for(int j=i+1;j<vlen;j++) {
                if(this.matrix[i][j]!=INF) {
                    edgeNum++;
                }
            }
        }
    }

    public void kruskal() {
        int index=0;  //表示最后结果数组的索引
        int[] ends=new int[edgeNum]; //表示已生成的"最小生成树"中的每个顶点在最小生成树中的终点
        //创建结果数组，保存最后的最小生成树
        EData[] rets=new EData[edgeNum];

        //获取图中所有的边的集合
        EData[] edges=getEdges();
        System.out.println("图的边的集合="+Arrays.toString(edges)+"共"+edges.length);

        //按照边的权值大小从小到大排序
        sortEdges(edges);

        //遍历edges数组，将边添加到最小生成树中时，判断准备加入的边是否形成了回路，如果没有，就加入rets，否则不能加入
        for(int i=0;i<edgeNum;i++) {
            //获取第i条边的第一个顶点
            int p1=getPosition(edges[i].start);
            //获取第i条边的第二个顶点
            int p2=getPosition(edges[i].end);

            //获取p1顶点在已有最小生成树的终点
            int m=getEnd(ends,p1);
            //获取p2顶点在已有最小生成树的终点
            int n=getEnd(ends,p2);

            //是否构成回路
            if(m!=n) {
                ends[m]=n;
                rets[index++]=edges[i];
            }
        }

        //统计并打印"最小生成树"，输出rets
        System.out.println("最小生成树为:");
        for(int i=0;i<index;i++) {
            System.out.println(rets[i]);
        }
    }

    //打印邻接矩阵
    public void print() {
        for(int i=0;i<vertex.length;i++) {
            for(int j=0;j<vertex.length;j++) {
                System.out.printf("%12d",matrix[i][j]);
            }
            System.out.println();  //换行
        }
    }

    /**
     * 功能:对边进行排序处理，冒泡排序
     * @param edges 边的集合
     */
    private void sortEdges(EData[] edges) {
        for(int i=0;i<edges.length-1;i++) {
            for(int j=0;j<edges.length-1-i;j++) {
                if(edges[j].weigh>edges[j+1].weigh){
                    EData temp=edges[j];
                    edges[j]=edges[j+1];
                    edges[j+1]=temp;
                    }
                }
        }
    }

    /**
     * 
     * @param ch 顶点的值，比如'A','B'
     * @return 返回ch顶点的下标，如果找不到就返回-1
     */
    private int getPosition(char ch) {
        for(int i=0;i<vertex.length;i++) {
            if(vertex[i]==ch) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 功能:获取图中的边，放到EData[]数组中，后面我们需要遍历数组
     * 通过matrix邻接矩阵获取
     * EData形式:[['A','B',12],['B','F',7],....]
     * @return 
     */
    private EData[] getEdges() {
        int index=0;
        EData[] edges=new EData[edgeNum];
        for(int i=0;i<vertex.length;i++) {
            for(int j=i+1;j<vertex.length;j++) {
                if(matrix[i][j]!=INF) {
                    edges[index++]=new EData(vertex[i],vertex[j],matrix[i][j]);
                }
            }
        }
        return edges;
    }

    /**
     * 功能:获取下标为i的顶点的终点,用于后面判断两个顶点的终点是否相同
     * @param ends 数组记录就是遍历过程中每次各个顶点的终点，动态的
     * @param i 表示传入顶点的对应下标
     * @return 返回的是终点对应的下标
     */
    private int getEnd(int[] ends,int i) {
        while(ends[i]!=0) {
            i=ends[i];
        }
        return i;
    }
}

class EData{
    char start;
    char end;
    int weigh;
    //构造器
    public EData(char start,char end,int weigh) {
        this.start=start;
        this.end=end;
        this.weigh=weigh;
    }

    @Override
    public String toString() {
        return "EData [<" + start + "," +end+ ">=" + weigh + "]";
    }

}