【程序员必会十大算法】之Prim算法

番茄西红柿发布于2021-09-28 09:36 / 3057人阅读

摘要：问题胜利乡有个村庄现在需要修路把个村庄连通各个村庄的距离用边线表示权比如距离公里问如何修路保证各个村庄都能连通并且总的修建公路总里程最短代码重点理解中的三层循环

问题

①胜利乡有7个村庄(A, B,C,D,E,F,G)，现在需要修路把7个村庄连通
②各个村庄的距离用边线表示(权)，比如A-B距离5公里
③问:如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?

代码

重点理解createMinTree中的三层for循环

public class Main {    public static void main(String[] args) {        char[] data = {'A','B','C','D','E','F','G'};        int[][] weight = {                {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,10006,10000,5,4},                {10000,10000,10000,4,5,10000,6},                {2,3,10000,10000,4,6,10000}};        MGraph mGraph = new MGraph(data.length);        mGraph.createGraph(data,weight);        mGraph.showGraph();        createMinTree(mGraph,0);    }    /**     *     * @param mGraph 表示图     * @param startIndex 表示开始的点的下标 比如从A开始，则传0     */    public static void createMinTree(MGraph mGraph,int startIndex){        if (mGraph.vertexNum == 0){            return;        }        //创建是否访问数组        boolean[] isVisited = new boolean[mGraph.vertexNum];        //全部初始化为 未访问        for (int i = 0;i < mGraph.vertexNum;i++){            isVisited[i] = false;        }        //将开始的点 设置成 已访问        isVisited[startIndex] = true;        //创建遍历到的两个点的下标        int v1 = -1;        int v2 = -1;        //创建两点间距离，默认不可达        int v1Tov2 = 10000;        //总共 遍历mGraph.vertexNum - 1 次，因为是一条边一条边遍历的，生成最小生成树的时候，边的数目==点的数目-1        for (int k = 0;k < mGraph.vertexNum - 1;k++){            //每一次都要遍历 已访问的节点集合 和 未访问的节点集合            //但是这个集合我们没创建出来，所以只能通过遍历所有的点，通过isVisited进行筛选            for (int i = 0;i < mGraph.vertexNum;i++){                for (int j = 0;j < mGraph.vertexNum;j++){                    //如果有一个点已经访问，另外一个点没有被访问，且两点间可达或者距离比当前记录的举例还要小                    if (isVisited[i] && !isVisited[j] && mGraph.weight[i][j] < v1Tov2){                        //将v1Tov2更新                        v1Tov2 = mGraph.weight[i][j];                        v1 = i;                        v2 = j;                    }                }            }            //遍历一次，得到两个点，即一个边，把这个边记录下来            System.out.println("边<"+ mGraph.data[v1] + "," + mGraph.data[v2]+"> 权值:"+ v1Tov2);            //然后为下一次遍历做初始化操作            isVisited[v2] = true;            v1Tov2 = 10000;        }    }}//这是图class MGraph{    //节点数目    int vertexNum;    //节点    char[] data;    //边的权值    int[][] weight;    MGraph(int vertexNum){        this.vertexNum = vertexNum;        data = new char[vertexNum];        weight = new int[vertexNum][vertexNum];    }    //图的创建    public void createGraph(char[] mData,int[][] mWeight){        if (vertexNum == 0){            return;//节点数目为0 无法创建        }        for (int i = 0;i < data.length;i++){            data[i] = mData[i];        }        for (int i = 0;i < mWeight.length;i++){            for (int j = 0;j < mWeight.length;j++){                weight[i][j] = mWeight[i][j];            }        }    }    //打印图    public void showGraph(){        if (vertexNum == 0){            return;        }        for (int[] oneLine: weight){            for (int oneNum: oneLine){                System.out.print(oneNum + " ");            }            System.out.println();        }    }}

结果

边<A,G> 权值:2边<G,B> 权值:3边<G,E> 权值:4边<E,F> 权值:5边<F,D> 权值:4边<A,C> 权值:7

云服务器 GPU云服务器最小生成树prim算法实验报告 webrtc之vad算法十大机器学习算法机器学习十大算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/121402.html

【程序员必会十大算法】之分治算法（汉诺塔问题）

摘要：应用分治法是一种很重要的算法。字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 ...

codecraft 2021-09-24 09:48 评论0 收藏0
【程序员必会十大算法】之二分查找算法

摘要：递归实现不考虑相同数二分查找，不考虑有相同数的情况递归找到了考虑有相同数二分查找考虑有相同元素的情况递归要查找的值 1.递归实现 ①不考虑相同数 /** * 二分查...

YFan 2021-09-24 09:48 评论0 收藏0
【程序员必会十大算法】之弗洛伊德算法

摘要：学习资料迪杰斯特拉计算的是单源最短路径，而弗洛伊德计算的是多源最短路径代码不能设置为，否则两个相加会溢出导致出现负权创建顶点和边学习资料迪杰斯特拉计算的是单源最...

JellyBool 2021-09-30 09:47 评论0 收藏0
【程序员必会十大算法】之贪心算法

摘要：例题假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。例题假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让...

macg0406 2021-09-27 13:36 评论0 收藏0
【程序员必会十大算法】之骑士周游问题

摘要：骑士周游问题又叫马踏棋盘问题未优化前没有策略定义棋盘的行数和列数定义棋盘上的某个点是否被访问过记录是否周游结束从第一行第一列开始走，第一次走算第一步，即展示下是棋盘， ...

Baoyuan 2021-09-30 09:47 评论0 收藏0