概念

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。

3.png

最小生成树其实是最小权重生成树的简称。

应用场景

是在工程上解决问题。

例如：城市与城市之间的路程，从一个城市到达另一个城市需要经过其他的城市，那么如何以最短的路径到达，这就需要找到带权的最小生成树来解决。

Kruskal算法实现

/**
 * 最小生成树，克鲁斯卡尔（kruskal）算法
 * author: bobo
 * create time: 2019/1/21 3:58 PM
 * email: jqbo84@163.com
 */
public class Kruskal {
    public int verticeSize;// 顶点的大小
    public int[][] matrix; // 邻接矩阵
    public int edgeSize;    //边的大小
    public Edge[] edges;

    public static final int I = 0xFFF8;

    public void init(int[][] matrix) {
        this.matrix = matrix;
        this.verticeSize = matrix.length;
    }

    /**
     * 获取所有的边
     *
     * @return
     */
    private Edge[] getEdges() {
        int index = 0;
        Edge[] edges = new Edge[verticeSize * verticeSize];
        for (int i = 0; i < verticeSize; i++) {
            for (int j = 0; j < verticeSize; j++) {
                if (matrix[i][j] != 0 && matrix[i][j] != I) {
                    edges[index++] = new Edge(i, j, matrix[i][j]);
                }
            }
        }
        edgeSize = index;
        return edges;
    }

    /**
     * 边的权重进行排序
     *
     * @param cur_edge
     * @param size
     */
    private void sortEdge(Edge[] cur_edge, int size) {
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (edges[i].weight > edges[j].weight) {
                    Edge tmp = edges[i];
                    edges[i] = edges[j];
                    edges[j] = tmp;
                }
            }
        }
    }

    /**
     * 克鲁斯卡尔 核心算法
     */
    public Edge[] kruskal() {
        edges = getEdges();
        int index = 0;
        Edge[] curEdges = edges;//存放排序后的边数组
        Edge[] rets = new Edge[edgeSize];//用来存放结果
        sortEdge(curEdges, edgeSize);//边的权重进行排序
        //定义一个数组，用来存放连通分量,用来表示连通关系的
        //下标用来表示起点,值表示终点
        int[] tempEdge = new int[edgeSize];
        for (int i = 0; i < edgeSize; i++) {
            int p1 = curEdges[i].start;
            int p2 = curEdges[i].end;
            int m = getEnd(tempEdge, p1);
            int n = getEnd(tempEdge, p2);
            //如果m和n没有连接在一起，他们就不相等
            //如果相等就有回路
            if (m != n) {
                rets[index++] = curEdges[i];
                if (m > n) {
                    int temp = n;
                    n = m;
                    m = temp;
                }
                tempEdge[m] = n;
            }
        }
        return rets;
    }

    /**
     * 获取当前节点的最后一个节点，也是当前链中最大值
     *
     * @param edges
     * @param p
     * @return
     */
    private int getEnd(int[] edges, int p) {
        int i = p;
        while (edges[i] != 0) {
            i = edges[i];
        }
        return i;
    }
        
    class Edge {
        int start; //起点
        int end; //终点
        int weight; //边的权重

        public Edge(){}

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }
}

Kruskal算法测试及结果

@Test
public void main(){
    int[][] m = new int[][]{
            {0,  50, 60,  I,  I,  I,  I},
            {50,  0,  I, 65, 40,  I,  I},
            {60,  I,  0, 52,  I,  I, 45},
            {I,  65, 52,  0, 50, 30, 42},
            {I,  40,  I, 50,  0, 70,  I},
            {I,   I,  I, 30, 70,  0,  I},
            {I,   I, 45, 42,  I,  I,  0}
    };

    init(m);
    Edge[] result = kruskal();

    int lengh = 0;
    for(int i = 0; i < result.length; i++) {
        if(null != result[i]){
            lengh+= result[i].weight;
        }
    }
    System.out.println("最小生成树的权重之和：" + lengh);
    char[] chars = new char[m.length];
    chars[0] = 'A';
    chars[1] = 'B';
    chars[2] = 'C';
    chars[3] = 'D';
    chars[4] = 'E';
    chars[5] = 'F';
    chars[6] = 'G';

    for (int i = 0; i < result.length; i++) {
        if(null != result[i]){
            System.out.printf("(%s, %s)---> %d \n",chars[result[i].start], chars[result[i].end], matrix[result[i].start][result[i].end]);
        }
    }
}

结果：
最小生成树的权重之和：257
(D, F)---> 30 
(E, B)---> 40 
(D, G)---> 42 
(G, C)---> 45 
(E, D)---> 50 
(A, B)---> 50 

1.png

Prim算法

**
 * author: bobo
 * create time: 2019/1/21 4:26 PM
 * email: jqbo84@163.com
 */
public class Prim {

    public static final int I = 0xFFF8;

    int SIZE = 7;//m为节点的个数

    //邻接矩阵
    int[][] G = new int[][]{
            {0,  28, I,  I,  I,  10,  I},
            {28,  0, 16, I, I,  I,  14},
            {I,  16,  0, 12,  I,  I, I},
            {I,  I, 12,  0, 22, I, 18},
            {I,  I,  I, 22,  0, 25,  24},
            {10,   I,  I, I, 25,  0,  I},
            {I,   14, I, 18,  24,  I,  0}
    };

    //最短路径数组, 对应的前驱索引值
    int[] path = new int[SIZE];

    //最短权重数组, 存放每次到另个顶点的修改后的权重值，先修改第一行V0
    int[] weight;

    //最小生成树的权重之和
    int minTree;

    /**
     * 普里姆核心算法
     */
    public void prim() {
        int k = 0;//表示当前正要处理的顶点Vk

        //初始化权重数组
        weight = G[0];

        //定义一个数组来存放集合U 和集合V 两个集合的顶点的信息
        boolean[] flag = new boolean[SIZE];
        //先从第一个顶点开始，所以先直接存放在U集合一边
        flag[0] = true;
        //开始逻辑,求VO到某个顶点的最短路径
        for (int v = 1; v < SIZE; v++) {
            //在能走的路径中找到最短的一条，也就是在集合V 中找
            int min = I;
            for (int i = 0; i < SIZE; i++) {
                if (!flag[i] && weight[i] < min) {
                    k = i;//K为U集合到V集合中找到的顶点
                    min = weight[i];//min找到了最小值的位置
                }
            }

            //如果min = I 表示已经不再有点可以加入最小生成树中
            if(min == I){
                break;
            }

            minTree += min;

            //找到最短路径后，把它存放在集合U中，然后从这个最短的路径对应的顶点开始找下一轮
            flag[k] = true;

            //path
            path[v] = k;

            for (int i = 0; i < SIZE; i++) {
                if(!flag[i] && weight[i] > G[k][i]){
                    weight[i] = G[k][i];   //更新可更新边的权值
                }
            }
        }
    }   
}

Prim算法测试及结果

@Test
public void main(){
    //普里姆算法
    prim();

    //打印
    System.out.print("最短路径：");
    for (int i = 0; i < path.length; i++) {
        System.out.print(path[i] + " ");
    }
    System.out.println();
    System.out.print("最短权重：");
    for (int i = 0; i < weight.length; i++) {
        System.out.print(weight[i] + " ");
    }

    System.out.println();
    System.out.println("最小生成树的权重之和 = " + minTree);
}

结果：
最短路径：0 5 4 3 2 1 6 
最短权重：0 16 12 22 25 10 14 
最小生成树的权重之和 = 99

2.png