最小生成树

最小生成树

Prime

普利姆(Prim)算法求最小生成树，也就是在包含 n 个顶点的连通图中，找出只有(n-1)条边包含所有 n 个顶点的连通子图，也就是所谓的极小连通子图?

import java.util.Arrays;

//普里姆算法
public class Prim {

    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int vertexs = 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},};
        MGraphy mGraphy = new MGraphy(vertexs);
        Prim prim = new Prim();
        prim.createGraphy(mGraphy, vertexs, data, weight);
        prim.showGraphy(mGraphy);
        prim.prim(mGraphy, 0);

    }

    ;


    /**
     * @param mGraphy 图对象
     * @param vertexs 图对应的节点的个数
     * @param data    图各个节点的数据
     * @param weight  图的邻接矩阵
     */
    public void createGraphy(MGraphy mGraphy, int vertexs, char data[], int[][] weight) {
        int i, j;
        for (int k = 0; k < vertexs; k++) {
            mGraphy.data[k] = data[k];
            for (int l = 0; l < vertexs; l++) {
                mGraphy.weight[k][l] = weight[k][l];
            }
        }
    }

    public void showGraphy(MGraphy mGraphy) {
        for (int[] link : mGraphy.weight) {
            //输出格式化
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * @param graphy 图
     * @param v      表示从第几个点开始生成
     */
    public void prim(MGraphy graphy, int v) {
        int visited[] = new int[graphy.vertexs];
        //visited[]默认元素为0，表示未访问
//        for (int i = 0; i < graphy.vertexs; i++) {
//            visited[i]=0;
//        }
        visited[v] = 1;//设置起始节点为已访问
        //h1和h2保存两个顶点的下标
        int h1 = -1, h2 = -1;
        int minWeight = 10000;//将当前找到的边是最短的
        for (int k = 1; k < graphy.vertexs; k++) {//prime算法结束后，有garph.vertexs-1条边

            //这个是确定每一次生成的子图 ，和哪个结点的距离最近
            for (int i = 0; i < graphy.vertexs; i++) {//i表示被访问的节点
                //j顶点表示未访问的节点
                for (int j = 0; j < graphy.vertexs; j++) {
                    //key!!!
                    if (visited[i] > 0 && visited[j] == 0 && graphy.weight[i][j] < minWeight) {
                        //找到当前最短的边
                        minWeight = graphy.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            //找到一条最小的边
            System.out.println("边<" + graphy.data[h1] + "," + graphy.data[h2] + "> 权值:" + minWeight);
            //将当前这个点标记为已访问节点
            visited[h2] = 1;
            //重新设置为最大值
            minWeight = 1000;
        }
    }
}
//内部类了解熟悉
class  MGraphy{
    int vertexs;//表示图的节点个数
    char[]data;//存储节点数据
    int[][]weight;//存储边，以及权重

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

Kruskal

?

import java.util.Arrays;

//按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路
        //问题一 对图的所有边按照权值大小进行排序
        //问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。
public class Kruskal {
    private int edgeNum;//边的个数
    private char[] vertexs;//顶点集合
    private int[][] matrix;//邻接矩阵
    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 = {
                {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}
        };
        Kruskal kruskal = new Kruskal(vertexs, matrix);
        //输出构建
        kruskal.print();
        kruskal.kruskal();
    }


    public Kruskal(char[] vertexs, int[][] matrix) {
        int vlen = vertexs.length;
        //初始化顶点，复制拷贝方式
        this.vertexs = new char[vlen];
        for (int i = 0; i < vlen; 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[]resultEdges=new Edata[edgeNum];

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

        //按照边的权值排序（小-》大）
        sortEdges(edges);
        //遍历 edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入resultEdges,否则不能加入
        for(int i=0;i<edges.length;i++){
            //获取到第 i 条边的第一个顶点(起点)
            int p1 =getPosition(edges[i].start);
            //获取到第 i 条边的第2个顶点(终点)
            int p2 =getPosition(edges[i].end);
            //获取 p1 这个顶点在已有最小生成树中的终点
            int m =getEnd(ends,p1);
            //获取 p2 这个顶点在已有最小生成树中的终点
            int n = getEnd(ends, p2);
            //是否构成回路
            if(m!=n) {//没有构成回路
                ends[m]=n;// 设置 m 在"已有最小生成树"中的终点
                resultEdges[index++]=edges[i];

            }
        }
        System.out.println("最小生成树为");
        for (int i = 0; i < index; i++) {
            System.out.println(resultEdges[i]);

        }
    }



    public void print() {
        System.out.println("邻接矩阵为：\n");
        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();
        }
    }

    public 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 temp = edges[j];
                    edges[j] = edges[j+1];
                    edges[j+1] = temp;
                }
            }
        }

    }

    /**
     * @param ch 顶点的值
     * @return 返回ch顶点对应下标
     */
    private int getPosition(char ch) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == ch) {//找到
                return i;
            }
        }
        return -1;
    }

    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){
//        key！！！
        while (ends[i]!=0){
            i=ends[i];
        }
        return i;
    }



}
//创建一个类 EData ，它的对象实例就表示一条边
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;
    }

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