十大常用算法之克鲁斯卡尔算法_随笔

十大常用算法之克鲁斯卡尔算法一、基本介绍 1、应用场景

2、克鲁斯卡尔算法介绍（1）描述

（2）分析

分析场景
图解算法

（3）克鲁斯卡尔算法回路分析

图解回路分析

二、代码实现

总的来说：要先根据节点来生成图，
对生成好的树：得到我们的数据变，进行排序的编写
然后还要对我们的判断是否会有回路的的情况
最后才是编写我们的算法
总的来说步骤有点多，但是不是很复杂的

1、首先来根据节点生成图

代码阅读建议

首先要明白我们的思想：是用二维数组【也就是矩阵】来进行存放两边是否连通
然后就先看我Mgraph类进行一步步的看着走就OK了

public class kruskalDemo {
    //用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[][] = {
                /*B*/
                 {   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的实例
        MGraph mGraph = new MGraph(vertexs,matrix);
        mGraph.print();
    }
}


class MGraph {
    //记录边的个数
    private int edgeNum;
    //顶点数组
    private char[] vertexs;
    //领接矩阵
    private int[][] matrix;


    //构造器
    public MGraph(char[] vertexs,int[][] matrix) {
        //初始化顶点树和边的个数
        int vlen = vertexs.length;//表示多少个顶点
        //初始化顶点，或者写this.vertexs = vertexs;我这里使用的是拷贝的方式
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }

        //初始化边，我这里使用的是拷贝的方式，或者写this.matrix = matrix
        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] != Integer.MAX_VALUE) {//说明之间是连通的
                    edgeNum++;
                }
            }
        }
    }

    //遍历一下领接矩阵
    public void print() {
        System.out.println("领接矩阵为：");
        System.out.println();
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%15d" , matrix[i][j]);
            }
            System.out.println();
        }
    }
}

2、去对边进行排序（1）编写表示我们边的一个类

//创建一个边类，它的实例表示一条边
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 "从边" +
                "start=" + start +
                "到" + end +
                "的权值为：" + weight +
                '}';
    }
}

（2）编写排序方法

这里开始有点乱的了，去看MGraph类中的如下方法【有方法一和方法二和方法三】
- getPosition方法：用来获取某一个顶点的下标
- getEdges方法：用来获取我们边的数组【就是我们刚才已经编写好的一个图里面，他们的每一个边都进行统计，方到一个数组里面，进行后续的排序】
- sortEdge：这个就是我们要排序的方法了

class MGraph {
    //记录边的个数
    private int edgeNum;
    //顶点数组
    private char[] vertexs;
    //领接矩阵
    private int[][] matrix;


    //构造器
    public MGraph(char[] vertexs,int[][] matrix) {
        //初始化顶点树和边的个数
        int vlen = vertexs.length;//表示多少个顶点
        //初始化顶点，或者写this.vertexs = vertexs;我这里使用的是拷贝的方式
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }

        //初始化边，我这里使用的是拷贝的方式，或者写this.matrix = matrix
        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] != Integer.MAX_VALUE) {//说明之间是连通的
                    edgeNum++;
                }
            }
        }
    }

    //遍历一下领接矩阵
    public void print() {
        System.out.println("领接矩阵为：");
        System.out.println();
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%15d" , matrix[i][j]);
            }
            System.out.println();
        }
    }

    
    public void sortEdge(EData[] edges) {
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - i - 1; j++) {
                if (edges[j].weight > edges[j+1].weight) {
                    //满足就要交换edges[j].weight > edges[j+1].weight
                    EData temp = edges[j];
                    edges[j] = edges[j+1];
                    edges[j+1] = temp;
                }
            }
        }
    }



    
    public 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] != Integer.MAX_VALUE) {
                    edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edges;
    }


    
    public int getPosition(char ch) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == ch) {//说明找到了
                return i;
            }
        }
        return -1;
    }
}

（3）来看这一步的测试

看第二部分测试

public class kruskalDemo {
    //用INF来表示两个顶点不能连通
    public static final int INF = Integer.MAX_VALUE;



    public static void main(String[] args) {
        //第一部分是测试第一步
        char[] vertexs = {'A','B','C','D','E','F','G'};
        int matrix[][] = {
                /*B*/
                 {   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的实例
        MGraph mGraph = new MGraph(vertexs,matrix);
        mGraph.print();



        //第二部分是测试第二部分的
        EData[] eData = mGraph.getEdges();//获取我们边的数组
        System.out.println("排序前 = " + Arrays.toString(eData));
        mGraph.sortEdge(eData);
        System.out.println("排序后 = " + Arrays.toString(eData));

    }
}

3、确定是否有回边的方法（1）方法的编写

在类MGraph里面增加一个方法getEnd：这个方法不好理解，但是它的目的在于判断最后的终点，到时候算法好进行处理：如果理解不了，暂时跳过这方法的想象，记住有这么一个方法就可以了

    public int getEnd(int[] ends,int i) {
        while (ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }

（2）到现在总体的方法：理解好思路，准备马上进行算法编写

package cn.mldn.kruskal;

import java.util.Arrays;

public class kruskalDemo {
    //用INF来表示两个顶点不能连通
    public static final int INF = Integer.MAX_VALUE;



    public static void main(String[] args) {
        //第一部分是测试第一步
        System.out.println("--------------------------------------------------");
        char[] vertexs = {'A','B','C','D','E','F','G'};
        int matrix[][] = {
                /*B*/
                 {   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的实例
        MGraph mGraph = new MGraph(vertexs,matrix);
        mGraph.print();



        //第二部分是测试第二部分的
        System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++=");
        EData[] eData = mGraph.getEdges();//获取我们边的数组
        System.out.println("排序前 = " + Arrays.toString(eData));
        mGraph.sortEdge(eData);
        System.out.println("排序后 = " + Arrays.toString(eData));


        //最后一部分的测试了
        System.out.println("======================================================");
        mGraph.kruskal();

    }
}

//创建一个边类，它的实例表示一条边
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 "从边" +
                "start=" + start +
                "到" + end +
                "的权值为：" + weight +
                '}';
    }
}


class MGraph {
    //记录边的个数
    private int edgeNum;
    //顶点数组
    private char[] vertexs;
    //领接矩阵
    private int[][] matrix;


    //构造器
    public MGraph(char[] vertexs,int[][] matrix) {
        //初始化顶点树和边的个数
        int vlen = vertexs.length;//表示多少个顶点
        //初始化顶点，或者写this.vertexs = vertexs;我这里使用的是拷贝的方式
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }

        //初始化边，我这里使用的是拷贝的方式，或者写this.matrix = matrix
        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] != Integer.MAX_VALUE) {//说明之间是连通的
                    edgeNum++;
                }
            }
        }
    }

    //遍历一下领接矩阵
    public void print() {
        System.out.println("领接矩阵为：");
        System.out.println();
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%15d" , matrix[i][j]);
            }
            System.out.println();
        }
    }

    
    public void sortEdge(EData[] edges) {
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - i - 1; j++) {
                if (edges[j].weight > edges[j+1].weight) {
                    //满足就要交换edges[j].weight > edges[j+1].weight
                    EData temp = edges[j];
                    edges[j] = edges[j+1];
                    edges[j+1] = temp;
                }
            }
        }
    }



    
    public 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] != Integer.MAX_VALUE) {
                    edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edges;
    }


    
    public int getPosition(char ch) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == ch) {//说明找到了
                return i;
            }
        }
        return -1;
    }


    
    public int getEnd(int[] ends,int i) {
        while (ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }
}

4、算法编写

在我们的MGraph里面添加方法五kruskal方法

带着这张图去理解
代码实现

public void kruskal() {
        int index = 0;//表示随后这个结果数组的索引【因为我们最后的数组俩面，要知道它多少条边】
        int[] ends = new int[edgeNum];//用于保存“已有最小生成树”中的每一个顶点在最小生成树中的终点
        //创建结果数组【将来我们最小生成树是以一个数组，就是最小边的一些集合】
        EData[] rets = new EData[edgeNum];

        //获取图中所有的边的集合，初始时候一共有12条边【你可以去数一数我们的那个图】
        EData[] edges = getEdges();
        System.out.println("获取图的边集合为" + edges.length);

        //按照边的权值进行从小到大进行排序
        sortEdge(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) {//m==n说明构成了回路
                //设置m在“最小生成树”中的终点
                ends[m] = n;
                rets[index++] = edges[i];//说明有一条表加入到rets里面的
            }
        }

        //统计并打印最小生成树【说白点就是输出一下rets】，如果有null的话是正确的啊，因为我们在12条边中选几条
        for (int i = 0; i < rets.length; i++) {
            if (rets[i] != null) {
                System.out.println(rets[i]);
            }
        }
        //最后来加一下它们的最小距离
        int num = 0;
        for (int i = 0; i < rets.length; i++) {
            if (rets[i] != null) {
                num += rets[i].weight;
                //为了好理解
                System.out.println(num);
            }
        }
    }

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/zaji/5635776.html

十大常用算法之克鲁斯卡尔算法

发表评论

评论列表（0条）