普利姆算法(Prim)的理解

        普利姆算法，应用于全通图构建最小生成树。

         比方说上图，有7个顶点。构建的最小生成树应该满足：用6(7-1)条边来连接这7个顶点，而且6条边的权值和最小。普利姆算法构建最小生成树的思路就是从点到线的进行构建。

        首先要把这个图表示出来：

        这样就表示好这个图了。

        有了图之后怎么构建最小生成树？思路如下： 

        从节点A开始寻找的话，步骤如下： 

        代码：

public class PrimAlgorithm {
    public static void main(String[] args) {
        //构建图
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};//节点名
        int verxs = data.length;
        int[][] value = 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,value);
        //minTree.showGraph(graph);

        minTree.prim(graph,1);
    }
}

//创建最小生成树:村庄图
class MinTree {
    //创建图的邻接矩阵

    
    public void createGraph(MGraph mGraph, int verxs, char[] data, int[][] value) {
        int i, j;
        for (i = 0; i < verxs; i++) {
            mGraph.data[i] = data[i];
            for (j = 0; j < verxs; j++) {
                mGraph.value[i][j] = value[i][j];
            }
        }
    }

    public void showGraph(MGraph mGraph) {
        for (int i = 0; i < mGraph.verxs; i++) {
            System.out.println(Arrays.toString(mGraph.value[i]));
            System.out.println();
        }
    }

    //普利姆算法生成最小生成树
    
    public void prim(MGraph graph,int verx){
        int visited[] = new int[graph.verxs];//visited代表节点是否访问过，遍历为1，未遍历为0

        visited[verx] = 1;//标记为已经访问过

        //定义h1，h2记录2个节点的下标
        int h1 = -1;
        int h2 = -1;
        //定义最小权值，一会寻找
        int minValue = 10000;//找到小的要替换掉

        //定义total记录总权值
        int total = 0;
        for (int i = 1; i < graph.verxs; i++) {//创建verxs - 1 条边的循环
            //下面的循环是穷举法，寻找最小的权值
            for (int j = 0; j < graph.verxs; j++) {//假设j节点是已经被访问过的节点，与k节点构成路径
                for (int k = 0; k < graph.verxs; k++) {//假设k节点未被访问
                    if (visited[j] == 1 && visited[k] == 0 && graph.value[j][k] < minValue){//在2节点中发现了更小的权值
                        minValue = graph.value[j][k];//更小的权值替换min
                        h1 = j;//
                        h2 = k;
                    }
                }
            }
            total += minValue;
            //找到了最小的边
            System.out.println("边<" + graph.data[h1] + "--" + graph.data[h2] + ">权值为：" + minValue);
            //将h2节点替换成已访问
            visited[h2] = 1;
            //重置min
            minValue = 10000;
        }

        System.out.println("总权值为：" + total);
    }
}

class MGraph {//创建图
    int verxs;//此图的节点数
    char[] data;//存放节点的数据
    int[][] value;//路径的权值

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