java普利姆算法(Prim)最小生成树修路问题代码实现

69 阅读 0 评论 46 点赞

我是靠谱客的博主殷勤蓝天，最近开发中收集的这篇文章主要介绍java普利姆算法(Prim)最小生成树修路问题代码实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

import java.util.Arrays;

/**
 * @author Drug
 * @create 2020-05-15 16:42
 */
public class Prim {
    public static void main(String[] args) {
        //测试看看图是否创建ok
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        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对象
        MGraph graph = new MGraph(verxs);
        //创建一个MinTree对象
        MinTree minTree = new MinTree();
        //图赋值
        minTree.createGraph(graph, verxs, data, weight);
        //展示图
//        minTree.showGraph(graph);
        //prim算法展示
        minTree.prim(graph,1);
    }
}

class MinTree{
    /**
     * 生成图
     * @param mGraph
     * @param verxs
     * @param data
     * @param weight
     */
    public void createGraph(MGraph mGraph,int verxs,char[] data,int[][] weight){
        //边数赋值
        for(int i = 0; i< weight.length;i++){
            //给点赋值
            mGraph.data[i] = data[i];
            for(int j = 0;j<weight[0].length;j++){
                //为边赋权值
                mGraph.weight[i][j] = weight[i][j];
            }
        }
    }

    /**
     * 展示图
     * @param mGraph
     */
    public void showGraph(MGraph mGraph){
        for (int[] link : mGraph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 普利姆算法
     * @param mGraph
     * @param v
     */
    public void prim(MGraph mGraph,int v){
        //表示各点是否被访问过,没被访问过默认为0
        int[] visited = new int[mGraph.verxs];
        //将初始点设置为1
        visited[v] = 1;
        //设置最小值,默认为10000
        int minValue = 10000;
        //记录最小值时候两个顶点
        int m = -1;
        int n = -1;
        //共需要点数-1条边
        for(int k=1;k<mGraph.verxs;k++){
            //初始化
            minValue = 10000;
            //遍历所有点和点之间的权值
            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] < minValue){
                        //为最小边记录信息
                        minValue = mGraph.weight[i][j];
                        m = i;
                        n = j;
                    }
                }

            }
            visited[n] = 1;
            //里循环结束时,minValue是最小边权值,m,n是最小边的点下标
            System.out.println("本轮最小边是 <"+mGraph.data[m]+"-"+mGraph.data[n]+" >" +" :权值是 " + mGraph.weight[m][n]);
        }
    }
}

class MGraph{
    //表示图的节点个数
    int verxs;
    //存放结点数据
    char[] data;
    //存放边，就是我们的邻接矩阵
    int[][] weight;

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