java实现最小生成树分别使用普里姆算法和克鲁斯卡尔算法

普里姆算法

package com.csw.algorithm.prem;

import com.csw.graph.Graph;

import java.util.Arrays;

/**
 * @Auther: 行路
 * @Date: Created on 2020/5/5 22:54 星期二
 * @Description: com.csw.algorithm.prem
 * @version: 1.0 普里姆算法
 */
public class PrimAlgorithm {
    public static void main(String[] args) {

        //测试图是否创建成功
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int vertex = data.length;
        //将领接矩阵的关系,使用二维数组来表示
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000},};
        //创建MGraph对象
        MGraph graph = new MGraph(vertex);
        //创建一个MinTree对象
        MinTree minTree = new MinTree();
        minTree.createGraph(graph,vertex,data,weight);
        //输出
        minTree.showGraph(graph);
        //测试普里姆算法
        minTree.prim(graph,0);
    }
}

//创建最小生成树->村庄的图

class MinTree {
    //创建图的领接矩阵

    /**
     * @param graph  图对象
     * @param vertex 图对应的顶点个数
     * @param data   图的各个顶点的值
     * @param weight 图的领接矩阵
     */
    public void createGraph(MGraph graph, int vertex, char[] data, int[][] weight) {
        int i, j;
        for (i = 0; i < vertex; i++) {
            graph.data[i] = data[i];
            for (j = 0; j < vertex; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }


    /**
     * 显示图的领接矩阵
     *
     * @param graph
     */
    public void showGraph(MGraph graph) {
        for (int[] link : graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }



    /**
     * 编写prim算法,得到最小生成树
     * @param graph 图
     * @param v 表示从图的第几个顶点开始生成
     */
    public void prim(MGraph graph,int v){
        //visited[] 标记节点是否被访问过
        int visited[]=new int[graph.vertex];
        //visited[] 默认元素的值都是0,表示没有访问过
//        for(int i=0;i<graph.vertex;i++){
//            visited[i]=0;
//        } 默认都是0
        //把当前这个节点标记未以访问
        visited[v]=1;
        //h1,h2记录两个顶点的下标
        int h1=-1;
        int h2=-1;
        int minWeight=10000; //将minWeight初始化成一个大数,后面在遍历过程中,会被替换
        for(int k=1;k<graph.vertex;k++){
            //因为有graph.vertex顶点,普里姆算法结束后,有graph.vertex-1边

            //这个是确定每一次生成的子图,和那个节点的距离最近
            for(int i=0;i<graph.vertex;i++){ //i节点被访问过的节点
                for(int j=0;j<graph.vertex;j++){ //j的节点表示还没有访问过的节点
                    if(visited[i]==1&&visited[j]==0&&graph.weight[i][j]<minWeight){
                        //替换minWeight(寻找已经访问过的节点和未访问过的节点间的权值最小的边)
                        minWeight=graph.weight[i][j];
                        h1=i;
                        h2=j;
                    }
                }
            }
            //找到一条边是最小的
            System.out.println("边<"+graph.data[h1]+","+graph.data[h2]+">权值:"+minWeight);
            //将当前找到的节点标记为已经访问
            visited[h2]=1;
            //minWeight重新设置为最大值10000
            minWeight=10000;
        }
    }
}

class MGraph {
    int vertex; //表示图的节点个数
    char[] data;//存放节点数据
    int[][] weight;//存放边,就是领接矩阵

    public MGraph(int vertex) {
        this.vertex = vertex;
        data = new char[vertex];
        weight = new int[vertex][vertex];
    }
}

克鲁斯卡尔算法

package com.csw.algorithm.kruskal;

import java.util.Arrays;

/**
 * @Auther: 行路
 * @Date: Created on 2020/5/6 10:48 星期三
 * @Description: com.csw.algorithm.kruskal
 * @version: 1.0 克鲁斯卡尔算法
 */
public class KruskalCase {

    private int edgeNum; //边的个数
    private char[] vertexs;//顶点数组
    private int[][] matrix; //领接矩阵
    //使用INF表示两个顶点不能联通
    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //克鲁斯卡尔算法的领接矩阵
        int matrix[][] = {
                //A B C D E F G
                {0, 12, INF, INF, INF, 16, 14}, //A
                {12, 0, 10, INF, INF, 7, INF},  //B
                {INF, 10, 0, 3, 5, 6, INF},     //C
                {INF, INF, 3, 0, 4, INF, INF},  //D
                {INF, INF, 5, 4, 0, 2, 8},      //E
                {16, 7, 6, INF, 2, 0, 9},       //F
                {14, INF, INF, INF, 8, 9, 0}};  //G
        //创建KruskalCase,对象实例
        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
        //输出构建
        kruskalCase.println();
        //输出边数
        //System.out.println(kruskalCase.edgeNum);

        //先得到边
        EData[] edges = kruskalCase.getEdges();

        //测试 未排序的
        System.out.println(Arrays.toString(edges));


        //排序后的结果
//        kruskalCase.sortEdges(edges);
//        System.out.println(Arrays.toString(edges));
        kruskalCase.kruskal();
    }

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

        //初始化顶点，复制拷贝的方式
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }
        //初始化边,使用复制拷贝方式
        this.matrix = new int[vlen][vlen];
        for (int i = 0; i < vlen; i++) {
            for (int j = 0; j < vlen; 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];

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

        //按照边的权值大小进行排序(从小到达)
        sortEdges(edges);
        //遍历 edges数组,将边添加到最小生成树中时判断是否形成了回路,如果没有就加入到结果数组中去,否则不能加入
        for (int i = 0; i < edgeNum; i++) {
            //获取得到第i条边的第一个顶点
            int p1 = getPosition(edges[i].start); //E的p1是 4
            //获取到第i条边的第2个顶点
            int p2 = getPosition(edges[i].end); // F的p2是5

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

            //获取p2这个顶点在已有最小生成树中的终点
            int n = getEnd(ends, p2); //n=5
            if (m != n) {
                //没有构成回路
                ends[m] = n; //设置m在已有最小生成树中的终点<E,F>[0,0,0,0,5,0,0,0,0,0]
                rets[index++] = edges[i]; //有一条边符合条件加入
            }
        }

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

    }


    /**
     * 打印领接矩阵
     */
    public void println() {
        System.out.println("领接矩阵为:");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.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].weight > edges[j + 1].weight) {
                    EData tmp = edges[j];
                    edges[j] = edges[j + 1];
                    edges[j + 1] = tmp;
                }
            }
        }
    }

    /**
     * @param ch 顶点的值,比如'A','B'
     * @return 返回ch顶点对应的下标, 如果找不到, 返回-1
     */
    public int getPosition(char ch) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[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 < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) {
                if (matrix[i][j] != INF) {
                    edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
                }
            }
        }
        return edges;
    }

    /**
     * 功能:获取下标为i的顶点的终点,用于判断两个顶点的终点是否相同
     *
     * @param ends:数组记录了各个顶点对应的终点是那个，ends数组是在遍历过程中逐步形成的
     * @param i                                         传入的顶点对应的下标
     * @return 返回就是下标为i的这个顶点对应的终点的下标
     */
    private int getEnd(int[] ends, int i) {
        while (ends[i] != 0) { //i是5 [0,0,0,0,5,0,0,0,0,0]
            i = ends[i];
        }
        return i;
    }

}

/**
 * Description: 创建一个类EData，它的对象实列就表示一条边
 *
 * @author Todcsw
 * @date
 */
class EData {
    char start;//边的一个点
    char end; //边的另外一个点
    int weight; //边的权值
    //构造器

    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    //重写toString，便于输出边

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