zcq
    Prim算法解决修路问题。

    1. package com.atguigu.prim;
    3. import java.util.Arrays;
    5. public class PrimAlgorithm {
    7.     public static void main(String[] args) {
    8.         //测试看看图是否创建ok
    9.         char[] data = new char[]{'A','B','C','D','E','F','G'};
    10.         int verxs = data.length;
    11.         //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
    12.         int [][]weight=new int[][]{
    13.             {10000,5,7,10000,10000,10000,2},
    14.             {5,10000,10000,9,10000,10000,3},
    15.             {7,10000,10000,10000,8,10000,10000},
    16.             {10000,9,10000,10000,10000,4,10000},
    17.             {10000,10000,8,10000,10000,5,4},
    18.             {10000,10000,10000,4,5,10000,6},
    19.             {2,3,10000,10000,4,6,10000},};
    21.         //创建MGraph对象
    22.         MGraph graph = new MGraph(verxs);
    23.         //创建一个MinTree对象
    24.         MinTree minTree = new MinTree();
    25.         minTree.createGraph(graph, verxs, data, weight);
    26.         //输出
    27.         minTree.showGraph(graph);
    28.         //测试普利姆算法
    29.         minTree.prim(graph, 1);// 
    30.     }
    32. }
    34. //创建最小生成树->村庄的图
    35. class MinTree {
    36.     //创建图的邻接矩阵
    37.     /**
    38.      * 
    39.      * @param graph 图对象
    40.      * @param verxs 图对应的顶点个数
    41.      * @param data 图的各个顶点的值
    42.      * @param weight 图的邻接矩阵
    43.      */
    44.     public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
    45.         int i, j;
    46.         for(i = 0; i < verxs; i++) {//顶点
    47.             graph.data[i] = data[i];
    48.             for(j = 0; j < verxs; j++) {
    49.                 graph.weight[i][j] = weight[i][j];
    50.             }
    51.         }
    52.     }
    54.     //显示图的邻接矩阵
    55.     public void showGraph(MGraph graph) {
    56.         for(int[] link: graph.weight) {
    57.             System.out.println(Arrays.toString(link));
    58.         }
    59.     }
    61.     //编写prim算法，得到最小生成树
    62.     /**
    63.      * 
    64.      * @param graph 图
    65.      * @param v 表示从图的第几个顶点开始生成'A'->0 'B'->1...
    66.      */
    67.     public void prim(MGraph graph, int v) {
    68.         //visited[] 标记结点(顶点)是否被访问过
    69.         int visited[] = new int[graph.verxs];
    70.         //visited[] 默认元素的值都是0, 表示没有访问过
    71. //        for(int i =0; i <graph.verxs; i++) {
    72. //            visited[i] = 0;
    73. //        }
    75.         //把当前这个结点标记为已访问
    76.         visited[v] = 1;
    77.         //h1 和 h2 记录两个顶点的下标
    78.         int h1 = -1;
    79.         int h2 = -1;
    80.         int minWeight = 10000; //将 minWeight 初始成一个大数，后面在遍历过程中，会被替换
    81.         for(int k = 1; k < graph.verxs; k++) {//因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边
    83.             //这个是确定每一次生成的子图 ，和哪个结点的距离最近
    84.             for(int i = 0; i < graph.verxs; i++) {// i结点表示被访问过的结点
    85.                 for(int j = 0; j< graph.verxs;j++) {//j结点表示还没有访问过的结点
    86.                     if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
    87.                         //替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边)
    88.                         minWeight = graph.weight[i][j];
    89.                         h1 = i;
    90.                         h2 = j;
    91.                     }
    92.                 }
    93.             }
    94.             //找到一条边是最小
    95.             System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);
    96.             //将当前这个结点标记为已经访问
    97.             visited[h2] = 1;
    98.             //minWeight 重新设置为最大值 10000
    99.             minWeight = 10000;
    100.         }
    102.     }
    103. }
    105. class MGraph {
    106.     int verxs; //表示图的节点个数
    107.     char[] data;//存放结点数据
    108.     int[][] weight; //存放边，就是我们的邻接矩阵
    110.     public MGraph(int verxs) {
    111.         this.verxs = verxs;
    112.         data = new char[verxs];
    113.         weight = new int[verxs][verxs];
    114.     }
    115. }