当前位置:首页 » 《关注互联网》 » 正文

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

16 人参与  2022年01月26日 15:24  分类 : 《关注互联网》  评论

点击全文阅读


问题

在这里插入图片描述
①胜利乡有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

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/33957.html

遍历  节点  访问  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 此去经年人未还霍沉洲沈青禾后续结局霍沉洲
  • 山海不相逢内容精选(温逸尘沈衿)_山海不相逢内容精选(温逸尘沈衿)
  • (番外)+(全书)霍沉洲沈青禾此去经年人未还(霍沉洲沈青禾)_(霍沉洲沈青禾此去经年人未还)列表_笔趣阁(霍沉洲沈青禾)
  • (番外)+(全书)霍沉洲沈青禾(此去经年人未还霍沉洲沈青禾)完结_(霍沉洲沈青禾)列表_笔趣阁(此去经年人未还霍沉洲沈青禾)
  • 「重回八零,拒绝替嫁冲喜」章节彩蛋限时释出‌_卫东玉兰苏夏人气小说未删减节选
  • 重生七零祁同伟不再是农民儿子结局+番外纯净版全书免费重生七零祁同伟不再是农民儿子结局+番外纯净版全书免费
  • 傅雅宁的神女老婆,却在背地承欢作乐顾尘傅雅宁全书在线
  • 全文神女老婆,却在背地承欢作乐全局(顾尘傅雅宁)列表_全文神女老婆,却在背地承欢作乐全局
  • (番外)+(全书)此去经年人未还全书+番外+后续免费下载_(沈青禾霍沉洲)此去经年人未还全书+番外+后续列表_笔趣阁(沈青禾霍沉洲)
  • 完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续列表_完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续(林梦婉)
  • 妻子辱我爸受贿自杀,我掏出一等军功章节选推荐_[陈素云辰朋友]小说精彩章节分享
  • 全书浏览苔藓爬满旧日诺言新上(顾砚廷慕晚夏)_苔藓爬满旧日诺言新上(顾砚廷慕晚夏)全书结局

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1