克鲁斯卡尔算法

一、问题引出

在这里插入图片描述

二、介绍

在这里插入图片描述

三、代码实现

package com.achang.algorithm;

import java.util.Arrays;

//克鲁斯卡尔算法
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.list();
        EData[] edges = kruskal.getEdges();
        System.out.println(Arrays.toString(edges));
        System.out.println("===========排序后");
        kruskal.sortEData(edges);
        System.out.println(Arrays.toString(edges));
        System.out.println("===========");
        kruskal.kruskal();//获取最小生成树
    }

    public Kruskal(char[] vertexs, int[][] matrix) {
        int vLen = vertexs.length;
        this.vertexs = vertexs;
        this.matrix = matrix;
        //统计边的数量
        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[] result = new EData[edgeNum];

        //获取图中所有边的集合
        EData[] edges = getEdges();
        //按照权值排序（从小到大）
        sortEData(edges);

        //将边添加到最小生成树中，并判断边是否发生回路
        for (int i = 0; i < edges.length; i++) {
            int p1 = getPosition(edges[i].start);
            int p2 = getPosition(edges[i].end);

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

            //判断是否构成回路，判断m与n是否相等
            if (m != n){
                //没有出现回路
                ends[m] = n;//设置m在已有最小生成树中的终点
                result[index++] = edges[i];//有条边加入到result中
            }
        }

        System.out.println("最小生成树："+Arrays.toString(result));
    }

    public void list() {
        System.out.println("邻接矩阵为：\n");
        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    //按照边的权值进行排序
    public void sortEData(EData[] eDatas) {
        for (int i = 0; i < eDatas.length - 1; i++) {
            for (int j = 0; j < eDatas.length - 1 - i; j++) {
                if (eDatas[j].weight > eDatas[j + 1].weight) {
                    EData temp = eDatas[j];
                    eDatas[j] = eDatas[j + 1];
                    eDatas[j + 1] = temp;
                }
            }
        }
    }

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

    /**
     * 获取图中的边，放到EData数组中，后面需要遍历该数组,通过matrix领接矩阵来获取
     */
    private EData[] getEdges() {
        int index = 0;
        EData[] eDatas = 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) {
                    eDatas[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
                }
            }
        }
        return eDatas;
    }

    /**
     * 获取下标为i的节点的终点
     *
     * @param ends 记录了各个节点对应的终点
     * @param i    传入的节点对应的下标
     * @return 下标为i的这个节点对应的终点的下标
     */
    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【star=t[" + start + "]，end=[" + end + "],weight=[" + weight + "]】";
    }
}