算法 - 普里姆算法(修路问题求解)

灰太狼 2023-07-03 12:08 75阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 2]

# 从A开始，A作为定点，找到与A相连并且未被处理(不在顶点集合中)的进行处理，找到权值最小的并加入集合，A-C\[7\]、A-G\[2\]、A-B\[5\]，最小的是A-G\[2\],所以把G加入集合，这里是有A-G的连接的。 #

# 然后把A、G作为顶点，找到与A、G相连未被处理的进行处理，A-C\[7\]、A-B\[5\]、G-E\[4\]、G-B\[3\]、G-F\[6\],最小的是G-B\[3\]，把B加入集合， #

# 直到全部遍历完成！ #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 3]

# 代码 #

package Algorithm.prim;
    
    import java.util.Arrays;
    
    public class PrimAlgorihm { 
        public static void main(String[] args) { 
            char data [] = new char[]{ 'A','B','C','D','E','F','G'};
            int verxs = data.length;
            int weight [][] = new int[][]{ 
                    { 10000,5,7,10000,10000,10000,2},
                    { 5,10000,10000,9,10000,10000,3},
                    { 7,10000,10000,10000,8,10000,1},
                    { 10000,9,10000,10000,10000,4,1},
                    { 10000,10000,8,10000,10000,5,4},
                    { 10000,10000,10000,4,5,10000,6},
                    { 2,3,10000,10000,4,6,10000},
            };
            MGraph mGraph = new MGraph(verxs);
            MinTree minTree = new MinTree();
            minTree.createGraph(mGraph,verxs,data,weight);
            minTree.showGraph(mGraph);
    
            //测试普里姆算法
            minTree.prim(mGraph,6);
        }
    }
    
    //创建最小生成树 ->
    class MinTree{ 
    
        //创建图的邻接矩阵
        /** * * @param graph 图对象 * @param verxs 顶点个数 * @param data 各个顶点的值 * @param weight 图的邻接矩阵 */
        public void createGraph(MGraph graph, int verxs, char [] data, int weight [][]){ 
            int i,j;
            for (i = 0; i < verxs; i++) { 
                graph.data[i] = data[i];
                for (j = 0; j < verxs; j++){ 
                    graph.weight[i][j] = weight[i][j];
                }
            }
        }
    
        //显示图的邻接矩阵
        public void  showGraph(MGraph graph){ 
            for (int [] link : graph.weight){ 
                System.out.println(Arrays.toString(link));
            }
        }
    
        //编写prim算法,得到最小生成树
    
        /** * * @param graph 图 * @param v 从图的哪个顶点开始生产 */
        public void prim(MGraph graph, int v){ 
            //visited[] 标记顶点是否被访问过，默认都为0
            int visited [] = new int[graph.verxs];
    
            //把当前节点标记为以访问
            visited[v] = 1;
            //用h1和h2记录两个顶点的下标
            int h1 = -1;
            int h2 = -1;
            int minWeight = 10000;//将minWeight先初始化为一个大数，后面遍历过程中会被替换
            for (int k = 0; k < graph.verxs -1; k++) { //因为有graph.verxs顶点，普里姆算法结束后，有graph.verxs-1边
                //这个是确定每一次生成的子图，和哪个节点的距离最近
                //就是把所有的节点都给遍历了，所有的线都遍历一遍，找到与当前顶点相连的未被访问过的
                for (int i = 0; i < graph.verxs; i++) { //i节点表示被访问过的节点
                    for (int j = 0; j < graph.verxs; j++) { //j节点表示未被访问过的节点
                        if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight){ 
                            //替换minWeight(寻找已经访问过的节点和未访问过的节点之间的权值最小的)
                            minWeight = graph.weight[i][j];
                            h1 = i;
                            h2 = j;
                        }
                    }
                }
                //找到一条边是最小的
                System.out.println("边 <" + graph.data[h1]+","+graph.data[h2]+"> 权值：" + minWeight);
                //把当前节点标记为已经访问过
                visited[h2] = 1;
                //重置minWeight
                minWeight = 10000;
            }
    
        }
    }
    class MGraph{ 
        int verxs; //图的节点个数
        char[] data;//保存节点数据
        int[][] weight;//存放边,邻接矩阵
    
        public MGraph(int verxs) { 
            this.verxs = verxs;
            data = new char[verxs];
            weight = new int[verxs][verxs];
        }
    
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020020613330242.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200206133519135.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200206133717504.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200206134834903.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70