关于java:我所知道的十大常用算法之普里姆算法

41次阅读

共计 3573 个字符,预计需要花费 9 分钟才能阅读完成。

前言需要


明天咱们学习的是普里姆算法,咱们还是从一个场景里引入看看

有 7 个村庄(A, B, C, D, E, F, G),当初须要修路把 7 个村庄连通

1. 各个村庄的间隔 用边线示意(权),比方 A – B 间隔 5 公里

2. 问 如何修路保障各个村庄都能连通,并且总的建筑公路总里程最短?

咱们的思路就是尽可能的抉择少的路线,并且每条路线最小,保障总里程数起码

一、什么是普里姆算法

普利姆 (Prim) 算法求:最小生成树就是在 蕴含 n 个顶点的连通图 中,找出 只有 (n-1) 条边蕴含所有 n 个顶点的连通子图,也就是所谓的极小连通子图

二、通过示例意识普里姆算法

其实修路的问题实质就是最小生成树的问题

先介绍一下最小生成树(Minimum Cost Spanning Tree),简称 MST

那么什么是最小生成树呢?其实就是给定一个 带权的无向连通图 ,如何 选取一棵生成树,使树上所有边上权的总和为最小。这叫最小生成树

那么最小生成树有什么特点呢?

1. 若有 N 个顶点,肯定要至多有 N - 1 条边
2. 图要蕴含全副顶点
3.N- 1 条边要都在图中

那么求最小生成树的算法次要有普里姆算法和克鲁斯卡尔算法

普里姆算法思路剖析

1. 设 G =(V,E)是连通网,T=(U,D)是最小生成树,V,U 是顶点汇合,E,D 是边的汇合

2. 若从顶点 u 开始结构最小生成树,则从汇合 V 中取出顶点 u 放入汇合 U 中,标记顶点 v 的 visited[u]=1

3. 若汇合 U 中顶点 ui 与汇合 V - U 中的顶点 vj 之间存在边,则寻找这些边中权值最小的边,但不能形成回路。

将顶点 vj 退出汇合 U 中,将边(ui,vj)退出汇合 D 中,标记 visited[vj]=1

4. 反复步骤②,直到 U 与 V 相等,即所有顶点都被标记为拜访过,此时 D 中有 n - 1 条边

普里姆算法图解思路剖析

1. 如果从 A 顶点开始解决,将 A 放入汇合中,并可连贯到其余顶点有 C、G、B

2. 此时这三条边的最小权重值是 A -G 为 2,于是咱们 G 放入汇合中,《A,G》

3. 此时这五条边的最小权重值是 B -B 为 3,于是咱们 B 放入汇合中,《A,G,B》

4. 此时这四条边的最小权重值是 G -E 为 4,于是咱们 E 放入汇合中,《A,G,B,E》

此时这五条边的最小权重值是 E -F 为 5,以此类推退出到汇合中 ….

最初的汇合后果应该是 <A,G,B,E,F,D,C>

普里姆代码思路剖析

1. 咱们须要一个寄存顶点的 char 数组,以及顶点的边数
2. 咱们须要应用邻接矩阵来示意顶点之间的连贯状况与权重值
3. 咱们须要生成 minTree 树
4. 咱们须要创立图

普里姆算法代码实际

1. 应用邻接矩阵来示意图所之间连贯关系与权重值

// 应用邻接矩阵形容权重值示意 0 代表无
int[][] weight = new int[][]{{0,5,7,0,0,0,2},
        {5,0,0,9,0,0,3},
        {7,0,0,0,8,0,0},
        {0,9,0,0,0,4,0},
        {0,0,8,0,0,5,4},
        {0,0,0,4,5,0,6},
        {2,3,0,0,4,6,0}
}; 

2. 须要一个寄存顶点的 char 数组,以及顶点的边数

//char[] 数组寄存顶点个数
char[] data = new char[]{'A','B','C','D','E','F','G'};

int verxs = data.length;

3. 创立图对象

class MGraph{

    int verxs;// 示意图的节点数
    char[] data;// 寄存结点数据
    int[][] weight;// 寄存边

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

4. 咱们须要将创立的这些值与数组、赋值给到图对象,并创立输入图的办法

class MinTree{

    // 创立图的邻接矩阵
    public void createGraph(MGraph graph,int verxs,char[] data,int[][] weight){for ( int i = 0 ; i<verxs;i++){
            // 将 char 数组里的值赋值给图
            graph.data[i] = data[i];
            for (int j = 0; j<verxs;j++){
                // 将 weight 里的值赋值给图
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    // 打印图的信息
    public void showGraph(MGraph graph){for ( int[] link : graph.weight){System.out.println(Arrays.toString(link));
        }
    }
}

接下来咱们应用 demo 实现图的创立与输入

public static void main(String[] args) {//char[] 数组寄存顶点个数
        char[] data = new char[]{'A','B','C','D','E','F','G'};

        // 顶点之间的边
        int verxs = data.length;

        // 应用邻接矩阵形容权重值示意 0 代表无
        int[][] weight = new int[][]{{0,5,7,0,0,0,2},
                {5,0,0,9,0,0,3},
                {7,0,0,0,8,0,0},
                {0,9,0,0,0,4,0},
                {0,0,8,0,0,5,4},
                {0,0,0,4,5,0,6},
                {2,3,0,0,4,6,0}
        };

        MGraph graph = new MGraph(verxs);
        MinTree minTree = new MinTree();
        minTree.createGraph(graph,verxs,data,weight);
        minTree.showGraph(graph);
}

依据普里姆算法思路编写算法代码

1. 咱们的思路是先找到一个顶点开始,一直找相邻顶点,比如说 A 开始

找相邻顶点的条件是: A 已拜访,其余顶点为未拜访

2.判断 A - 其余顶点的 weight,是否是最小的

为了不便找到最小的,咱们这里应用一个很大的数,来代替刚刚的:0

public void prim(MGraph graph,int v){
        // 应用数组标注节点是否被拜访过
        int[] visited = new int[graph.verxs];

        for (int i=0; i<visited.length; i++){visited[i] = 0;
        }

        // 将以后节点标注为已拜访
        visited[v] = 1;

        int h1 = -1;
        int h2 = -1;
        int minWeight = 10000;
        for(int k = 1; k < graph.verxs; k++) {for(int i = 0; i < graph.verxs; i++) {for(int j = 0; j< graph.verxs;j++) {if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            System.out.println("边 <" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);
            visited[h2] = 1;
            minWeight = 10000;
        }
    }

行将上图所至的0 --> 10000

public static void main(String[] args) {//char[] 数组寄存顶点个数
    char[] data = new char[]{'A','B','C','D','E','F','G'};

    // 顶点之间的边
    int verxs = data.length;

    // 应用邻接矩阵形容权重值示意 0 代表无
    int[][] weight = new int[][]{{10000,5,7,10000,10000,10000,2},
            {5,10000,10000,9,10000,10000,3},
            {7,10000,10000,10000,8,10000,10000},
            {10000,9,10000,10000,10000,4,10000},
            {10000,10000,8,10000,10000,5,4},
            {10000,10000,10000,4,5,10000,6},
            {2,3,10000,10000,4,6,10000}
    };

    MGraph graph = new MGraph(verxs);
    MinTree minTree = new MinTree();
    minTree.createGraph(graph,verxs,data,weight);
    minTree.showGraph(graph);
    minTree.prim(graph,0);
}

运行后果如下:边 <A,G> 权值:2
边 <G,B> 权值:3
边 <G,E> 权值:4
边 <E,F> 权值:5
边 <F,D> 权值:4
边 <A,C> 权值:7

参考资料


  • 尚硅谷:数据结构与算法(韩顺平老师):普里姆算法

正文完
 0