欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-16 08:53:08
...

图的最小生成树

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

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

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

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

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


普利姆算法(prim)

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

prim算法的核心思想:

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

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

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

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

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

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

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

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

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

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

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

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

  1. 以A、G、B、E、F、D为起点找最短边
    最短边是<A,C>=7,将C加入visited集合,发现所有顶点都加入了visited集合,得到了最小生成树
    经典算法 - 图解图的最小生成树问题与prim、kruskal算法

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

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


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];
    }

}

最终结果:

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


克鲁斯卡尔算法(kruskal)

kruskal算法核心思想:

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

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

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

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

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

具体可以分析后面的代码

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

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

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

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

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

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

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

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

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

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

  • 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的选择

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

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