Kruskal算法

和Prim算法一样，也是求最小生成树的，先补并查集部分知识，对于Kruskal算法的“判断该节点属于哪一类”可以有更深刻的理解。

如上图，给城市的公交站修路，使得所有点连通，同时总路径最小。

思路

1. 克鲁斯卡尔算法，是用来求加权连通图的最小生成树的算法。
2. 基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
3. 做法：
   • 将边按权值从小到大排序
   • 不断将按边的权值从小到大加入森林，同时保证森林中不产生回路，直到选择了n-1条边。

图解

1. 首先有n个顶点，则需选择n-1条边

2. 第一步选择E-F[2]边

   

3. 第二步，选择C-D[3]边

   

4. 第三步，选择D-E[4]边

   

5. 第四步，拟选择C-E[5]但是发现构成回路，不能选；拟选择C-F[6]但是发现构成回路，不能选；故选择B-F[7]。

   

6. 第五步，选择E-G[8]

   

7. 第六步，拟选择F-G[9]构成回路，不能选；拟选择B-C[10]，构成回路，不能选；故选择A-B[11]

   

8. 已选择$n-1$，即6条边，最小生成树已生成。最后结果为：E-F[2]、C-D[3]、D-E[4]、B-F[7]、E-G[8]、A-B[11]

上述过程中，有两个问题需要解决：

1. 将边按权值从小到大排序，这个易解决

2. 每次新加入边时，需判断是否会构成回路，这个要利用并查集：

   • 以下面状态举例：
   • 此时：
     • C的终点节点为F
     • D的终点节点为F
     • E的终点节点为F
     • F的终点节点为F
   • 如果新加入的边，其两个节点的终点节点相同，比如C-E[5]，C和E的终点节点都为F，用并查集里面的术语来讲，C与E就是同一树上的节点，此时若连接C与E，则会构成回路。

   不懂什么意思就看看并查集这种数据结构。

代码实现

KruskalDemo

package com.yukinoshita.algorithm.kruskal;

import java.util.Arrays;

public class KruskalDemo {
    private static final int INF =Integer.MAX_VALUE;
    public static void main(String[] args){
        char[] vertexs = {'A','B','C','D','E','F','G'};
        //此处构造是，自身顶点是0，是跟后续“并查集”的算法有关
        // 即，while(i != 0) { i = ends[i]; }，去找到"根节点"，判断某两条边是否是"同一个集合"，防止回路生成
        int[][] matrix = {
                {0, 11, INF, INF, INF, 13, 12},
                {11, 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},
                {13, 7, 6, INF, 2, 0, 9},
                {12, INF, INF, INF, 8, 9, 0}
        };
                Kruskal kruskal = new Kruskal(vertexs, matrix);
//                kruskal.print();
                kruskal.createMinTree();
    }
}


class Kruskal{
    private int edgeNum;//边的个数
    private char[] vertexs;//顶点集合
    private int[][] matrix;//邻接矩阵

    Edge[] edges;//所有边

    private static final int INF =Integer.MAX_VALUE;
    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 < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                this.matrix[i][j] = matrix[i][j];
            }
        }

        //统计边的个数
        for(int i = 0; i < matrix.length; i++){
            for(int j = i+1; j < matrix[i].length; j++){
                if(matrix[i][j] != INF){
                    this.edgeNum++;
                }
            }
        }
        edges = getEdges();
    }

    private Edge[] getEdges(){
        Edge[] edges1 = new Edge[this.edgeNum];
        int k = 0;
        //给边赋值（由于是无向图，只需遍历上三角（不包括自身））
        for(int i=0;i<matrix.length;i++){
            for(int j=i+1;j<matrix[i].length;j++){
                if(matrix[i][j] != INF){
                    edges1[k++] = new Edge(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        Arrays.sort(edges1);
        return edges1;
    }

    //pirnt
    public void print(){
        for(int i=0;i<matrix.length;i++){
            System.out.println(Arrays.toString(matrix[i]));
        }
        System.out.println("打印边，"+"总共"+edges.length+"条边：");
        for(int i=0;i<edges.length;i++){
            System.out.println(edges[i]);
        }
    }

    //返回对应站点的下标  'A' -> 0，找不到则-1
    private int getPosition(char ch){
        for(int i=0;i<vertexs.length;i++){
            if(vertexs[i] == ch){
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取下标为i的顶点对应的“终点”节点 对应的下标
     * 用于后续判断，新加入的边是否会造成回路
     * @param ends 记录每个顶点的终点的数组，初始化时，每个顶点的终点都是自身
     * @param i 传入的顶点对应下标
     * @return 获取下标为i的顶点对应的“终点”对应的下标
     */
    private int getEnd(int[] ends,int i){
        if(i != ends[i]){
            return ends[i] = getEnd(ends,ends[i]);
        }
        return i;
    }

    //生成最小生成树算法
    public void createMinTree(){
        int index = 0;
        int[] ends = new int[edgeNum];//用于保存 当前已有边的顶点的集合中 每个顶点的终点
        for(int i=0;i<ends.length;i++){//用并查集的思路，给所有节点的 根节点 设置为其自身，也就是各自为一棵树
            ends[i] = i;
        }

        Edge[] result = new Edge[vertexs.length-1];//保存最后结果（最后只需顶点数 - 1 条边即可）

        //edges是在构造时，已经按照边的权值从小到大拍好的Edge数组
        //对边edges进行遍历
        for(int i=0;i<edgeNum;i++){
//            //优化
//            if(index == vertexs.length){
//                break;//此时已经能将所有顶点练成最小生成树，后面的边没必要遍历了
//            }

            //获取当前边的两个顶点的下标
            int p1 = getPosition(edges[i].start);
            int p2 = getPosition(edges[i].end);

            //获取当前边两个顶点各自的终点
            int m = getEnd(ends,p1);
            int n = getEnd(ends,p2);

            //若没有构成回路
            if(m != n){
//                ends[m] = getEnd(ends,n);//将边m的终点设置为n的终点（做了一个压缩路径！）
                ends[m] = n;//设置m的终点
                result[index++] = edges[i];//有一条边加入结果中
            }
        }

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

    }
}

//边的类
class Edge implements Comparable<Edge>{
    char start;//起点
    char end;//终点
    int weight;//权
    public Edge(char start, char end, int weight){
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        return weight - o.weight;
    }

    @Override
    public String toString() {
        return "Edge{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}