经典算法 - 图解图的最小生成树问题与prim、kruskal算法

图的最小生成树

前面介绍了图：数据结构 - 图与深度优先、广度优先遍历
生成树：无向图G的生成子图是连通且不含回路的无向图，称为G的生成树

现有一个图：有7个顶点{'A','B','C','D','E','F','G'}，顶点间长度为权值

现要保证所有顶点连通且长度最短

这个问题就是求最小生成树，有两种经典的算法：prim、kruskal算法

---

普利姆算法（prim）

prim算法的核心思想：

1. 从起点开始，每次都找到该起点的权值最小的边
2. 将该边的另一个顶点加入集合visited，然后找visited集合中所有顶点的权值最小的边（已被访问的顶点为起点，未被访问的顶点为终点）
3. 重复2步骤，直到所有顶点都被访问

如上图，使用prim算法求最小生成树的步骤：

1. 假设起点为A，找A的边集合中最小边，也就是<A,G>=2，将G加入visited集合

2. 找visited集合中所有顶点的权值最小的边，也就是以A、G为起点找最短边
   这里最短边是<G,B>=3，将B加入visited集合

3. 找visited集合中所有顶点的权值最小的边，也就是以A、G、B为起点找最短边
   这时最短边是<G,E>=4，将E加入visited集合

4. 以A、G、B、E为起点找最短边
   这时的最短边为<E,F>=5，将F加入visited集合

5. 以A、G、B、E、F为起点找最短边
   四条边里最短边为<F,D>=4，将D加入visited集合

6. 以A、G、B、E、F、D为起点找最短边
   最短边是<A,C>=7，将C加入visited集合，发现所有顶点都加入了visited集合，得到了最小生成树
   

最终得到最小生成树：同时也能算出总长为25

---

Java代码实现prim算法

代码中需要注意：

• 用邻接矩阵保存图的边、权值，用INF = 65535表示两条边不能连接
• 需要两个对象：MGraph图对象，MinTree最小生成树对象
• prim算法思路如上图，下面是代码实现

package com.company.十种算法.prim;

import java.util.Arrays;

/**
 * Author : zfk
 * Data : 16:37
 * prim算法 - 》 最小生成树
 */
public class PrimAlgorithm {

    //用INF表示两个顶点不能连通
    private static final int INF = 65535;

    public static void main(String[] args) {

        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        //邻接矩阵
        int[][] weight = new int[][]{
                {INF,5,7,INF,INF,INF,2},
                {5,INF,INF,9,INF,INF,3},
                {7,INF,INF,INF,8,INF,INF},
                {INF,9,INF,INF,INF,4,INF},
                {INF,INF,8,INF,INF,5,4},
                {INF,INF,INF,4,5,INF,6},
                {2,3,INF,INF,4,6,INF}
        };

        //创建MGraph对象
        MGraph mGraph = new MGraph(verxs);
        //创建MinTree
        MinTree minTree = new MinTree();
        minTree.createGraph(mGraph,verxs,data,weight);

        minTree.showGraph(mGraph);
        minTree.prim(mGraph,0);
    }


}

//创建最小生成树
class MinTree{

    /**
     * 创建图的邻接矩阵
     * @param graph 图对象
     * @param verxs 顶点个数
     * @param data 顶点的值
     * @param weight 图的邻接矩阵
     */
    public void createGraph(MGraph graph,int verxs,char[] data,int[][] weight){

        int i ,j;
        for (i = 0;i < verxs;i++){
            graph.data[i] = data[i];
            for (j = 0;j < verxs;j++){
                graph.weight[i][j] = weight[i][j];
            }
        }

    }

    public void showGraph(MGraph graph){
        for (int[] link : graph.weight){
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 编写prim算法，得到最小生成树
     * @param mGraph 图
     * @param v 生成树的起点
     */
    public void prim(MGraph mGraph,int v){
        //标记已被访问的顶点,初始都为0
        int[] visited = new int[mGraph.verxs];

        //把当前节点标记为已访问
        visited[v] =1;
        //用h1和h2记录两个顶点的下标
        int h1 = -1 , h2 = -1;
        //存储最小权
        int minWeight = 10000;

        for (int k =1;k < mGraph.verxs;k++){
            //i表示访问过的节点，j表示没有访问过的节点
            for (int i = 0;i < mGraph.verxs;i++){
                for (int j =0;j < mGraph.verxs;j++){
                    //当<i,j>的边权值小于最小值,存储两顶点，即找到最小边
                    if (visited[i] == 1 && visited[j] == 0 &&
                            mGraph.weight[i][j] < minWeight){
                        minWeight = mGraph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }

                }
            }
            //找到1条边最小
            System.out.println("边<"+mGraph.data[h1]+","+mGraph.data[h2]+"> 权值："+minWeight);
            //标记已访问
            visited[h2] =1;
            //重新设置为最大值 10000
            minWeight = 10000;
        }
    }

}


//图
class MGraph{
    //结点个数
    int verxs;
    //存放结点数据
    char[] data;
    //邻接矩阵：存放边
    int[][] weight;

    public MGraph(int verxs){
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }

}

最终结果：

---

克鲁斯卡尔算法（kruskal）

kruskal算法核心思想：

1. 先把边按权值从小到大排序（自选排序算法）
2. 顺序将边加入结果集合（如果加入该边会造成回路就抛弃这条边，继续判断下一条）

kruskal算法关键在第二步：判断加入边是否会造成回路

可以设置一个终点集合ends（终点为最大的顶点，<A,G>的终点为G），最小生成树每加入一个边，就将树中的每个顶点在最小生成树中的终点更新，如果加入的两个顶点的终点相同，说明构成了回路

具体可以分析后面的代码

如上图，使用kruskal算法求最小生成树的步骤：

1. 根据边权值大小排序：

2. 按顺序加入边，判断边<A,G>，初始ends集合中A,G终点不相同，加入，并把A、G的终点设置为G

3. 判断边<B,G>，ends集合中B的终点为B，A的终点为G，加入，并把B的终点设置为G

4. 判断边<D,F>，ends集合中D,F的终点为D,F，加入，并把D,F的终点设置为F

5. 判断边<E,G>，ends集合中E的终点为E，G的终点为G，加入，并把E的终点设置为G

6. 判断边<A,B>，ends集合中A的终点为G，B的终点为G，两个终点相同，跳过该边

7. 后续重复上述操作，直到所有边都判断完成

关于判断终点、判断回路的两个方法：

• getEnd方法：获取下标为i的顶点的终点，当ends[i]为0，即并没有设置终点，就直接返回i，等待后续加入边时来设置终点
• kruskal方法：其中每次得到一个边的两个顶点，都用getEnd方法获得终点，如该两点终点值不同，就将该边加入结果集，同时更新两个顶点的终点值

注：具体看后续完整代码，最初添加边时设置了start\end顶点，所有这里不需要考虑p1,p2的大小

    /**
     * 获取下标为i的顶点的终点，用于判断回路
     * @param ends 该数组记录了各个顶点对应的终点
     * @param i 传入顶点对应的下标
     * @return 返回下标为i的顶点对应的终点的下标
     */
    private int getEnd(int[] ends,int i){
        while (ends[i] != 0){
            i = ends[i];
        }
        return i;
    }


 	public void kruskal(){
        //表示结果数组的索引
        int index = 0;
        //用于保存已有最小生成树中的每个顶点在最小生成树中的终点
        int[] ends = new int[edgeNum];
        //创建结果数组,保存最后的最小生成树,且长度为顶点数-1
        EData[] result = new EData[vertexs.length-1];

        //获取图中所有的边的集合
        EData[] edges = getEdges();
        //放入的边，按照权值大小排序
        sortEdge(edges);
        //将边添加到最小生成树，需要判断是否构成回路
        //没有就加入result
        for (int i = 0;i < edgeNum;i++){
            //获取第i条边的第一个顶点
            int p1 = getPosition(edges[i].start);
            //获取第i条边的第二个顶点
            int p2 = getPosition(edges[i].end);

            //获得p1,p2两个点在已有的最小生成树的终点
            int m = getEnd(ends,p1);
            int n = getEnd(ends,p2);
            //判断是否构成回路
            if (m != n){//不构成
                //设置m在已有最小生成树的终点
                ends[m] = n;
                result[index++] = edges[i];
            }
        }
        //统计并打印最小生成树
        System.out.println("最小生成树："+ Arrays.toString(result));


    }

---

Java代码实现kruskal算法

这里偷一下懒使用冒泡排序，如果追求效率可以选快速排序等

package com.company.十种算法.kruskal;

import java.util.Arrays;

/**
 * Author : zfk
 * Data : 8:24
 * Kruskal算法
 */
public class KruskalCase {
    //边数
    private int edgeNum;
    //顶点数组
    private char[] vertexs;
    //邻接矩阵
    private int[][] matrix;
    //用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 = {
                {INF,5,7,INF,INF,INF,2},
                {5,INF,INF,9,INF,INF,3},
                {7,INF,INF,INF,8,INF,INF},
                {INF,9,INF,INF,INF,4,INF},
                {INF,INF,8,INF,INF,5,4},
                {INF,INF,INF,4,5,INF,6},
                {2,3,INF,INF,4,6,INF}
        };

        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);

        kruskalCase.print();


        EData[] edges = kruskalCase.getEdges();

        kruskalCase.sortEdge(edges);
        for (EData eData : edges){
            System.out.println(eData);
        }
        kruskalCase.kruskal();


    }

    public KruskalCase(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 < 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] != INF){
                    edgeNum++;
                }
            }
        }

    }


    public void kruskal(){
        //表示结果数组的索引
        int index = 0;
        //用于保存已有最小生成树中的每个顶点在最小生成树中的终点
        int[] ends = new int[edgeNum];
        //创建结果数组,保存最后的最小生成树,且长度为顶点数-1
        EData[] result = new EData[vertexs.length-1];

        //获取图中所有的边的集合
        EData[] edges = getEdges();
        //放入的边，按照权值大小排序
        sortEdge(edges);
        //将边添加到最小生成树，需要判断是否构成回路
        //没有就加入result
        for (int i = 0;i < edgeNum;i++){
            //获取第i条边的第一个顶点
            int p1 = getPosition(edges[i].start);
            //获取第i条边的第二个顶点
            int p2 = getPosition(edges[i].end);

            //获得p1,p2两个点在已有的最小生成树的终点
            int m = getEnd(ends,p1);
            int n = getEnd(ends,p2);
            //判断是否构成回路
            if (m != n){//不构成
                //设置m在已有最小生成树的终点
                ends[m] = n;
                result[index++] = edges[i];
            }
        }
        //统计并打印最小生成树
        System.out.println("最小生成树："+ Arrays.toString(result));


    }

    //打印邻接矩阵
    public void print(){
        System.out.println("=== 邻接矩阵 ===");
        for (int i = 0;i < vertexs.length;i++){
            for (int j = 0;j < vertexs.length;j++){
                System.out.printf("%10d\t",matrix[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 对边进行排序
     * @param edges 边的集合
     */
    private void sortEdge(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[j+1].weight){
                    EData temp = edges[j];
                    edges[j] = edges[j+1];
                    edges[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邻接矩阵获取
     * @return
     */
    private 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] != INF){
                    edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }

        return edges;
    }

    /**
     * 获取下标为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 " { " +
                "<" + start +
                " , " + end +
                ">  weight=" + weight +
                " } ";
    }
}

结果：

还是那个最小生成树

---

关于prim与kruskal的选择

从上面的解析过程其实可以看出：

• prim算法是直接查找，多次寻找邻边的权重最小值；Kruskal是需要先对权重排序后查找的，设置优秀的排序算法，kruskal的效率更高
• prim算法是循环顶点；kruskal是循环边。所以当顶点很多边少选kruskal好些；当边很多顶点少，选prim好些