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

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

11 人参与  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