Java十大算法之克鲁斯卡尔算法

应用场景:

1.克鲁斯卡尔算法介绍

克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法,基本思想:按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路,具体做法:首先构造一个只含有n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直到森林变成一棵树为止

接下来用图解的方式进行一下分析:

上面的连通网,不同的连通方式,权值总和是不一样的,以本图为例,进行克鲁斯卡尔演示:

(1)第一步

(2)第二步

(3)第三步

(4)第四步,虽然EC,FC的距离都比BF短,但是我们依然选取BF,因为EC,FC都构成短路(关于什么是短路,在演示结束会讲解)

(5)第五步

(6)第六步

克鲁斯卡尔算法分析:

克鲁斯卡尔算法重点需要解决两个问题

(1)对图的所有边按照权值大小进行排序?

解决:采用排序算法进行排序即可.

(2)将边添加到最小生成树中时,怎么样判断是否形成了回路?

记录顶点在"最小生成树"中的终点,顶点的终点是"在最小生成树中与它连通的最大顶点",然后每次需要将一条边添加到最小生成树时,判断该边的两个顶点的终点是否重合,重合的话则会构成回路

图解说明:

在将<E,F>,<C,D>,<D,E>加入到最小生成树R中之后,这几条边的顶点就都有了终点

C的终点是F

D的终点是F

E的终点是F

F的终点是F

关于终点的说明:就是将所有顶点按照从小到大的顺序排列好之后,某个顶点的终点就是"与它连通的最大顶点",因此,接下来,虽然<C,E>是权最小的边,但是C和E的终点都是F,即他们终点相同,因此,将<C,E>加入最小生成树的话,会形成回路,这就是回路的判断方式,也就是说,我们加入的边的两个顶点不能都指向同一个终点,否则构成回路

代码实现

package com.self.tenAlgorithm;

import java.util.Arrays;

public class KruskaCase {
    private char[] vertexs;  //顶点
    private int edgeNum;  //边的个数
    private int[][] matrix;  //邻接矩阵
    private static final int INT = Integer.MAX_VALUE;
    public static void main(String[] args) {
        char[] vertexs = {'A','B','C','D','E','F','G'};
        int[][] matrix = {
                {0,12,INT,INT,INT,16,14},
                {12,0,10,INT,INT,7,INT},
                {INT,10,0,3,5,6,INT},
                {INT,INT,3,0,4,INT,INT},
                {INT,INT,5,4,0,2,8},
                {16,7,6,INT,2,0,9},
                {14,INT,INT,INT,8,9,0}
        };
        KruskaCase kruskaCase = new KruskaCase(vertexs, matrix);
        kruskaCase.print();

        EData[] egdes = kruskaCase.getEgdes();
        System.out.println(Arrays.toString(egdes));
        System.out.println("==========================================================");
        kruskaCase.sortEdges(egdes);
        System.out.println(Arrays.toString(egdes));
        System.out.println("==========================================================");
        kruskaCase.kruskal();
    }

    /**
     * @param vertexs  顶点数组
     * @param matrix  邻接矩阵
     */
    //构造器
    public KruskaCase(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] != INT){
                    edgeNum ++;
                }
            }
        }
    }
    public void kruskal(){
        int index = 0;  //表示最后结果数组的索引
        int[] ends = new int[edgeNum];//用于保存已有"最小生成树"中的每个顶点在最小生成树中的终点
        //创建结果数组,保存最小生成树
        EData[] rets = new EData[edgeNum];
        //获取图中所有边的集合
        EData[] egdes = getEgdes();
        //按照权值从小到大排序
        sortEdges(egdes);
        //遍历edges数组,将边添加到最小生成树,判断准备加入的边是否构成了回路,如果没有,就加入rets,否则不能加入
        for (int i = 0; i < edgeNum; i++) {
            //获取到第i条边的第一个顶点(起点)  下标
            int p1 = getPosition(egdes[i].start);
            //获取第i条边的第2个顶点  下标
            int p2 = getPosition(egdes[i].end);

            //获取p1这个顶点在已有最小生成树中的终点
            int m = getEnd(ends, p1);
            int n = getEnd(ends,p2);
            if(m != n){  //判断是否构成了回路  不等于 没有构成回路
                ends[m] = n;  //设置m在"已有最小生成树"中的终点
                rets[index++] = egdes[i];  //有一条边加入到rets数组
            }
        }
        //统计并打印"最小生成树",输出rets
        System.out.println("最小生成树为:");
        for (int i = 0; i < index; i++) {
            System.out.println(rets[i]);
        }
    }

    /**
     * 打印邻接矩阵
     */
    public void print(){
        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[i].weight){
                    EData temp = edges[j];
                    edges[j] = edges[i];
                    edges[i] = temp;
                }
            }
        }
    }

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

    /** 获取图中边 放到EData[] 数组中  后面我们需要遍历数组
     * @return  形式['A','B',12]
     */
    private EData[] getEgdes(){
        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] != INT){
                    edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edges;
    }

    /**功能:获取下标为i的顶点的终点,用于后面判断两个顶点的终点是否相同
     * @param ends 记录各个顶点对应的终点是哪一个,endss数组是在遍历的过程中,逐步生成
     * @param i  表示对应的顶点对应的下标
     * @return  返回的就是这个顶点对应的下标
     */
    private int getEnd(int[] ends,int i){
        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=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}